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
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 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
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. 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.
-
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, 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 January 13, 2011
Technical support: <webmaster@nada.kth.se>