Let $G = (V, E)$ be an undirected, unweighted graph. I wish to assign weights (possibly negative, not all zero) to the edges to minimize the value of: $$\frac{m}{\|w\|}$$ where $m$ is the value of the maximum magnitude cut on the new weighted graph, and $w$ is the $|E|$-length vector containing the new edge weights.

What is the smallest I can make $\frac{m}{\|w\|}$? Can I make it $o(1)$ (little-oh)? Is there a polynomial time procedure for generating some $w$ that comes within a constant factor of the best value for $\frac{m}{\|w\|}$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.