Approximation algorithms

Researcher

Johan Håstad

Ph.D. student

Per Austrin

Alumni

Lars Engebretsen Ph.D. May 2000
Gustav Hast Ph.D. June 2005
Jonas Holmerin, Ph.D. December 2002
Viggo Kann, Ph.D. May 1992
Anna Palbom Licentiate, 2006

Short description

A large number of the known NP-complete problems are in fact optimization problems, and for some of these optimization problems there are fast approximation algorithms, i.e. algorithms guaranteed to find close to optimal solutions. For example, the travelling salesperson problem in the plane is NP-complete, but in polynomial time it can be solved approximately within every constant, i.e. for any e>0 one can find a trip of length at most 1+e times the shortest trip possible. On the other hand, some NP-complete problems are extremely hard to approximate. For example, unless P=NP the maxmum independent set problem cannot in polynomial time be approximated within n^(1-e) for any e>0, where n is the number of vertices in the input graph.

The main topic of this project is to investigate to what extent the optimum value of important NP-complete problems can be approximated effectively. These investigations are naturally divided into two types of activities, namely to prove positive and negative approximation results. To get a positive result - an upper bound of the approximability - one constructs an algorithm, proves that it is efficient and approximates the problem within a certain accuracy. To get a negative result - a lower bound - one usually proves that approximating a given problem remains NP-hard.

Some of our most startling negative results finally close the gap between the upper and lower bounds of the approximability of problems such as finding the largest clique and finding the largest number of simultaneously satisfiable 3-CNF-SAT clauses.

A recent focus point of the project has been approximability of maximum constraint satisfaction problems. A recent highlight is the result of Austrin showing that balanced instances of Max-2Sat are in fact not the most difficult to approximate.

For a more detailed overview of the area end the current goals of the project please concult this slight abridged version of our recent project plan submitted to ERC.

Viggo Kann and Pierluigi Crescenzi have compiled a list of the best lower and upper bounds known for more than two hundred well-studied NP-complete optimization problems. We try to collect all new results in the wide area of approximation in order to keep the problem list updated. The list is included in a new text book on approximation, and is also available for everybody on the web as http://www.nada.kth.se/~viggo/problemlist/. It has been frequently used by researchers through the world for several years.

Funding

The project has been funded 1993-1999 by TFR and since 2001 by The Swedish Research Council. An expansion of the project starting in 2009 is funded by the European Research Council.

Given the generous founding of ERC we are currently looking for nw graduate students within this project and the application is due on January 14, 2009. Announcements in English and Swedish.

Old Publications

This list of publications is being updated, please be patient.

Some optimal in-approximability results: J. Håstad; Journal of ACM, Vol 48: 798-859, 2001; An earlier version was presented at STOC-97, 1-10, 1997.; PDF.
Clique is hard to approximate within n^1-eps: J. Håstad; Acta Mathematica 182:105-142, 1999; An earlier version was presented at FOCS-96.; PDF.
Towards optimal lower bounds for Clique and Chromatic Number: L. Engebretsen and J. Holmerin; Theoretical Computer Science 299, 2003. (PDF); A preliminary version of this paper won the best student paper award at ICALP '00.
Vertex Cover on 4-uniform Hypergraphs is Hard to Approximate Within 2 - epsilon: J. Holmerin; Technical Report TR01-094, Electronic Colloquium on Computational Complexity, December 2001. ECCC Report. In STOC/Complexity 2002.
Improved Inapproximability Results for Vertex Cover on k-uniform Hypergraphs: J. Holmerin; Appeared in ICALP 2002.
Inapproximability Results for Equations over Finite Groups: L. Engebretsen, J. Holmerin and A. Russell; Technical Report TR02-030, Electronic Colloquium on Computational Complexity, June 2002. ECCC Report. Accepted to Theoretical Computer Science. A preliminary version appeared in ICALP 2002.
Three-Query PCPs with Perfect Completeness over non-Boolean Domains: L. Engebretsen, J. Holmerin; Technical Report TR02-040, Electronic Colloquium on Computational Complexity, July 2002. ECCC Report.
On Probabilistic Proof Systems and Hardness of Approximation: J. Holmerin; PhD Thesis 2002. (PDF) (Postscript); This thesis won the Swedish Association of Scientist's award for best PhD thesis in computer science 2002.
Some New Randomized Approximation Algorithms: G. Andersson; Ph.D. thesis, May 2000.; Technical report TRITA-NA-0009, NADA, KTH
Approximate Constraint Satisfaction: L. Engebretsen; Ph.D. thesis, April 2000.; Technical report TRITA-NA-0008, NADA, KTH
Complexity and Approximation - Combinatorial optimization problems and their approximability properties: G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi; Published by Springer Verlag in November 1999, ISBN 3-540-65431-3.; More information about the book.
A compendium of NP optimization problems: P. Crescenzi and V. Kann; A list of NP complete optimization problems and their approximability.; The list is updated continuously.
Structure in approximation classes: P. Crescenzi, V. Kann, R. Silvestri, L. Trevisan; SIAM J. Computing 28:1759-1782, 1999.; COCOON 95, pages 539-548, LNCS 959, 1995.; Postscript.
An Approximation Algorithm for Max p-Section: G. Andersson; STACS-99, pages 237-247, LNCS 1563, March 1999.
An Explicit Lower Bound for TSP with Distances One and Two: L. Engebretsen; STACS-99, pages 373-382, LNCS 1563, March 1999.; ECCC, TR98-046, August 1998.; HTML.
A New Way to Use Semidefinite Programming With Applications to Linear Equations mod p: G. Andersson, L. Engebretsen and J. Håstad; SODA-99, pages 41-50, 1999.
How to find the best approximation results - a follow-up to Garey and Johnson: P. Crescenzi and V. Kann; ACM SIGACT News, volume 29, number 4, December 1998, pages 90-97; HTML.
Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems: G. Andersson and L. Engebretsen; RANDOM 98, pages 357-368, LNCS 1518, October 1998.; Postscript.
Better approximation algorithms for Set splitting and Not-all-equal sat: G. Andersson and L. Engebretsen; IPL, 65(6):305-311, April 1998.; ECCC report TR97-022, 1997; HTML, Postscript.
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems: E. Amaldi, V. Kann; Theoretical Computer Science 209:237-260, 1998.; Postscript.
Approximate Max k-cut with subgraph guarantee: V. Kann, J. Lagergren, A. Panconesi; IPL, 65:145-150, 1998.; ASHCOMP-96, 1996.; Postscript.
On the hardness of approximating MAX k-CUT and its dual: S. Khanna, V. Kann, J. Lagergren, A. Panconesi; Chicago J. Theoretical Computer Science, number 1997:2, June 1997.; ISTCS-96, pages 61-67, 1996.; NADA report TRITA-NA-9505, 1995.; Postscript.
Hardness of approximating problems on cubic graphs: P. Alimonti, V. Kann; CIAC 97, 288-298, LNCS 1203, 1997.; ASHCOMP-96, 1996.; Theoretical Computer Science, 237:123-134, 2000.; Postscript.
Hardness of approximation: V. Kann, A. Panconesi; Chapter 2 in Dell'Amico, Maffioli, Martello (editors), Annotated Bibliographies in Combinatorial Optimization, Wiley, 1330, 1997.; Postscript.
Linearity Testing in Characteristic Two: M. Bellare, D. Coppersmith, J. Håstad, M. Kiwi, and M. Sudan; IEEE Transactions on Information Theory, Vol 42, No 6, November 1996, pp 1781-1796; PDF.
On the approximability of the Steiner tree problem in phylogeny: D. Fernández-Baca, J. Lagergren; ISAAC-96, pages 65-74, LNCS 1178, 1996.
Approximability of maximum splitting of k-sets and some other APX-complete problems: V. Kann, J. Lagergren, A. Panconesi; IPL, 58:105-110, 1996.; NADA report TRITA-NA-9512, 1995.; Postscript.
Strong lower bounds on the approximability of some NPO PB-complete maximization problem: V. Kann; MFCS 95, pages 227-236, LNCS 969, 1995.; NADA report TRITA-NA-9501, 1995.; Postscript.
Polynomially bounded minimization problems that are hard to approximate: V. Kann; Nordic Journal of Computing 1:317-331, 1994.; ICALP 93, LNCS 700, 1993.; Postscript.
The complexity and approximability of finding maximum feasible subsystems of linear relations: E. Amaldi, V. Kann; Theoretical Computer Science 147:181-210, 1995.; STACS 94, LNCS 775, 1994.; NADA report TRITA-NA-9313, 1993.; Postscript.
On the approximability of some NP-hard minimization problems for linear systems: E. Amaldi, V. Kann; ECCC report TR96-015, 1996; International Symposium on Mathematical Programming, Ann Arbor, 1996; Tech. report 95-7, Cornell Computational Optimization Project, Cornell University, Ithaca, NY, 1995.; HTML, Postscript.

Up to Research, Theory group at Nada, KTH.

Responsible for this page: Johan Håstad <johanh@nada.kth.se>
Latest change December 18, 2008
Technical support: <webmaster@nada.kth.se>