^ Up to Research, Theory group at Nada, KTH.

Approximation algorithms

Job opening

We are currently looking for a Postdoc on NP-hard optimization problems. Apply by Februari 15, 2011.

Researcher Leader

Johan Håstad

Post Docs

Graduate students


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 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. This list has not been updated since around 2001-2002 but is a good source for older results. The list is included in a text book on approximation, and is also available for everybody on the web as


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.

Old Publications

This list of publications is being updated updated at irregular intervals, if you do not find what you want contact the author of the paper you are looking for.
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.
Randomly Supported Independence and Resistance
P. Austrin and J. Håstad
To appear in SIAM J on Computing
Conditional Hardness of Precedence Constrained Scheduling on Identical Machines
O. Svensson
STOC 2010, pages 745-754
Santa Claus Schedules Jobs on Unrelated Machines
O. Svensson
Approximating Linear Threshold Predicates
M. Cheraghchi, J. Håstad, M. Isaksson and O. Svensson
Approx 2010 LNCS 6302, pp 110-123.
Every 2-CSP allows nontrivial approximation
J. Håstad
Computational Complexity, Volume 17, 2008, pages 549-566 PDF.
On the approximation resistance of a random Preciate
J. Håstad
Approx 2007, LNCS 4627, 2007, pages 149-163. PDF.
Query efficient PCPs with perfect completeness
J. Håstad and S. Khot
Theory of Computing, Vol 1, 2005, pages 119-149. PDF.
On the advantage over a random assignment
J. Håstad and V. Srinivasan
Random Structures and Algorithms}, Vol 25, 2004, pages 117-149. PDF.
Simple Analysis of graph tests for linearity and PCP
J. Håstad and A. Wigderson
Random Structures and Algorithms}, Vol 22, 2003, pages 139-160. 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.
Hardness of Approximate Hypergraph Coloring
V. Guruswami, J. Håstad, and M. Sudan
, SIAM Journal on Computing, Vol 31, 2002, pages 1663-1686 PDF.
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.
Linear consistency testing
Y. Aumann, J. Håstad, M. Rabin, and M. Sudan
, Journal of Computer and System Science, Vol 62, 2001, pages 589-607 PDF.
A New Way to Use Semidefinite Programming With Applications to Linear Equations mod p
G. Andersson, L. Engebretsen and J. Håstad
Journal of Algorithms, Vol 39, 2001, pages 162-204.
On bounded occurence constraint satisfaction
J. Håstad
Information Processing Letters, Vol 74, 2000, pages 1-6. PDF.
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
Clique is hard to approximate within n1-eps
J. Håstad
Acta Mathematica 182:105-142, 1999
An earlier version was presented at FOCS-96.
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.
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.
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
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.
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.
Approximate Max k-cut with subgraph guarantee
V. Kann, J. Lagergren, A. Panconesi
IPL, 65:145-150, 1998.
ASHCOMP-96, 1996.
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.
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.
Hardness of approximation
V. Kann, A. Panconesi
Chapter 2 in Dell'Amico, Maffioli, Martello (editors), Annotated Bibliographies in Combinatorial Optimization, Wiley, 13­30, 1997.
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
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.
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.
Polynomially bounded minimization problems that are hard to approximate
V. Kann
Nordic Journal of Computing 1:317-331, 1994.
ICALP 93, LNCS 700, 1993.
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.
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 <>
Latest change January 13, 2011
Technical support: <>