bild
School of
Electrical Engineering
and Computer Science

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

Approximation algorithms

Research Leader

Johan Håstad, Professor.

Researcher

Post Doc(s)

Vacant.

Graduate student(s)

Alumni

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 maximum 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 highlight is the result of Austrin showing that balanced instances of Max-2Sat are in fact not the most difficult to approximate. Other directions have been to understand what makes a predicate "approximation resistant" and to extend the available techniques to other types of problems such as machine scheduling.

Another success of the project is the new approximation algorithm for the TSP in the metric case by Moemke and Svensson.

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 http://www.nada.kth.se/~viggo/problemlist/.

Funding

The project has been funded 1993-1999 by TFR and since 2001 by The Swedish Research Council and ran in small scale. During 2009-2014 we have more activity due to an advanced grant from ERC. Currently the project is back to smaller scale with financing from the Swedish Research Council.

Old Publications

This list of publications below is being updated but should be seen as examples of results coming out of the project. For modern publications please consult the member's webpages.
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.
Randomly Supported Independence and Resistance
P. Austrin and J. Håstad
To appear in SIAM J on Computing
PDF.
Conditional Hardness of Precedence Constrained Scheduling on Identical Machines
O. Svensson
STOC 2010, pages 745-754
PDF.
Santa Claus Schedules Jobs on Unrelated Machines
O. Svensson
Submitted
PDF.
Approximating Linear Threshold Predicates
M. Cheraghchi, J. Håstad, M. Isaksson and O. Svensson
Approx 2010 LNCS 6302, pp 110-123.
PDF.
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.
PDF.
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.
PDF.
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.
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, 13­30, 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.

Published by: Johan Håstad <johanh@nada.kth.se>
Updated 2015-09-25