BICKER - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

This is an NP-hard problem more commonly known as sparsest cut. One observation is that in each test case it is always possible to find an answer with value 2 according to the scoring mechanism. This follows from the observation that we can always cut at least 1/2 of the total d-values through a simple greedy algorithm. Process the nodes one at a time and, at each step, we can either place the current node in S or in T. Choose the one that separates the most d-value among the edges from v to nodes appearing in S or T; at least half of the d-value of these edges is then separated. Since each edge is “introduced” once and at least half of the d-value is separated at each step, then at least half of the total d-value is cut. This is a good starting point for a heuristic, but it completely ignores the q-values. There are examples (with optimum score close to 0) where this heuristic performs very poorly.

In general, the best approximation algorithm is O(sqrt(log n) * loglog n) 1. If all d-values are 1 (i.e. d(u,v) = 1 for all u != v in V) then there is a slightly better O(sqrt(log n)) 2approximation. However, they both require techniques from “semidefinite programming”, a generalization of linear programming. More practically, there are linear programming based O(log n) approximations that are quite easy to implement given an LP solver [3,4].

  1. S. Arora, J.R. Lee, and A. Naor, Euclidean distortion and the sparsest cut. Journal of the American Mathematical Society, 21:1-21, 2008.

  2. S. Arora, S. Rao, and U. Vazirani, Geometry, flows, and graph-partitioning algorithms. Communications of the ACM, 51:96-105, 2008.

  3. T. Leighton and S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In proceedings of IEEE Foundations of Computing Science, 422-431, 1988.

  4. N. Linial, E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithm applications. Combinatorica, 15:215-245, 1995.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.