PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This is an NPhard 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 dvalues 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 dvalue among the edges from v to nodes appearing in S or T; at least half of the dvalue of these edges is then separated. Since each edge is “introduced” once and at least half of the dvalue is separated at each step, then at least half of the total dvalue is cut. This is a good starting point for a heuristic, but it completely ignores the qvalues. 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 dvalues 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].

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

S. Arora, S. Rao, and U. Vazirani, Geometry, flows, and graphpartitioning algorithms. Communications of the ACM, 51:96105, 2008.

T. Leighton and S. Rao, An approximate maxflow mincut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In proceedings of IEEE Foundations of Computing Science, 422431, 1988.

N. Linial, E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithm applications. Combinatorica, 15:215245, 1995.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.