The breakthrough theory of iterative compression introduced by Reed, Smith and Vetta [1] can give positive answers to a number of open problems of parameterized complexity of several important NP-hard minimization problems, such as Vertex Bipartization Problem, Undirected Feedback Vertex Set, Directed Feedback Vertex Set, Almost 2-SAT, etc. Iterative compression can solve the Vertex Bipartization in $O(3^k|V||E|)$.

Iterative rounding is a very successful research in approximation algorithms[2], which lead to an approximation algorithm for the Steiner Tree Problem with the best theoretical approximation guarantee[3]. A recent DIMACS challenge on Steiner Tree Problem workshop has a good experimental result of implementation of Iterative rounding[4].

My Question: Can Iterative Compression lead minimization NP-hard problem to both in low complexity and good approximation?

[1] Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299–301 (2004)

[2] Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization. Cambridge University Press, 2011.

[3] Jaros law Byrka, Fabrizio Grandoni, Thomas Rothvoss, and Laura Sanita. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1{6:33, February 2013.

[4] Ciebiera, Krzysztof, et al. "Approximation Algorithms for Steiner Tree Problems Based on Universal Solution Frameworks." arXiv preprint arXiv:1410.7534 (2014). http://dimacs11.cs.princeton.edu/workshop.html


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.