Up to Research, Theory group at Nada, KTH.
Approximation algorithms
Job opening
We are currently looking for a
Postdoc on NPhard 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 NPcomplete 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 NPcomplete,
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 NPcomplete problems are extremely hard
to approximate. For example, unless P=NP the maxmum independent
set problem cannot in polynomial time be approximated within
n^(1e) 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 NPcomplete 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 NPhard.
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 3CNFSAT 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
Max2Sat 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 wellstudied
NPcomplete optimization problems. This list has not been
updated since around 20012002 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 19931999 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 inapproximability results
 J. Håstad
 Journal of ACM, Vol 48: 798859, 2001
 An earlier version was presented at STOC97, 110, 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 745754

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 110123.

PDF.
 Every 2CSP allows nontrivial approximation
 J. Håstad
 Computational Complexity, Volume 17, 2008, pages 549566
PDF.
 On the approximation resistance of a random Preciate
 J. Håstad
 Approx 2007, LNCS 4627, 2007, pages 149163.
PDF.
 Query efficient PCPs with perfect completeness
 J. Håstad and S. Khot
 Theory of Computing, Vol 1, 2005, pages 119149.
PDF.
 On the advantage over a random assignment
 J. Håstad and V. Srinivasan
 Random Structures and Algorithms}, Vol 25, 2004, pages 117149.
PDF.
 Simple Analysis of graph tests for linearity and PCP
 J. Håstad and A. Wigderson
 Random Structures and Algorithms}, Vol 22, 2003, pages 139160.
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 4uniform Hypergraphs is Hard to Approximate Within 2  epsilon
 J. Holmerin
 Technical Report TR01094, 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 16631686
PDF.
 Improved Inapproximability Results for Vertex Cover on kuniform Hypergraphs
 J. Holmerin
 Appeared in ICALP 2002.
 Inapproximability Results for Equations over Finite Groups
 L. Engebretsen, J. Holmerin and A. Russell
 Technical Report TR02030, Electronic Colloquium on Computational Complexity, June 2002.
ECCC Report. Accepted to Theoretical Computer Science. A preliminary version appeared in ICALP 2002.
 ThreeQuery PCPs with Perfect Completeness over nonBoolean Domains
 L. Engebretsen, J. Holmerin
 Technical Report TR02040, 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 589607
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 162204.
 PDF.
 On bounded occurence constraint satisfaction
 J. Håstad
 Information Processing Letters, Vol 74, 2000, pages 16.
PDF.
 Some New Randomized Approximation Algorithms
 G. Andersson
 Ph.D. thesis, May 2000.
 Technical report TRITANA0009, NADA, KTH
 Approximate Constraint Satisfaction
 L. Engebretsen
 Ph.D. thesis, April 2000.
 Technical report TRITANA0008, NADA, KTH
 Clique is hard to approximate within n^{1eps}
 J. Håstad
 Acta Mathematica 182:105142, 1999
 An earlier version was presented at FOCS96.

PDF.
 Complexity and Approximation  Combinatorial optimization problems and their approximability properties
 G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann,
A. MarchettiSpaccamela, M. Protasi
 Published by Springer Verlag in November 1999, ISBN 3540654313.
 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:17591782, 1999.
 COCOON 95, pages 539548, LNCS 959, 1995.

Postscript.
 An Approximation Algorithm for Max pSection
 G. Andersson
 STACS99, pages 237247, LNCS 1563, March 1999.
 An Explicit Lower Bound for TSP with Distances One and Two
 L. Engebretsen
 STACS99, pages 373382, LNCS 1563, March 1999.
 ECCC, TR98046, August 1998.

HTML.
 How to find the best approximation results  a followup to Garey and Johnson
 P. Crescenzi and V. Kann
 ACM SIGACT News, volume 29, number 4, December 1998, pages 9097
 HTML.
 Sampling Methods Applied to Dense Instances of NonBoolean Optimization Problems
 G. Andersson and L. Engebretsen
 RANDOM 98, pages 357368, LNCS 1518, October 1998.
 Postscript.
 Better approximation algorithms for Set splitting and Notallequal sat
 G. Andersson and L. Engebretsen
 IPL, 65(6):305311, April 1998.
 ECCC report TR97022, 1997

HTML,
Postscript.
 On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
 E. Amaldi, V. Kann
 Theoretical Computer Science 209:237260, 1998.

Postscript.
 Approximate Max kcut with subgraph guarantee
 V. Kann, J. Lagergren, A. Panconesi
 IPL, 65:145150, 1998.
 ASHCOMP96, 1996.

Postscript.
 On the hardness of approximating MAX kCUT and its dual
 S. Khanna, V. Kann, J. Lagergren, A. Panconesi
 Chicago J. Theoretical Computer Science, number 1997:2, June 1997.
 ISTCS96, pages 6167, 1996.
 NADA report TRITANA9505, 1995.

Postscript.
 Hardness of approximating problems on cubic graphs
 P. Alimonti, V. Kann
 CIAC 97, 288298, LNCS 1203, 1997.
 ASHCOMP96, 1996.
 Theoretical Computer Science, 237:123134, 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 17811796
 PDF.
 On the approximability of the Steiner tree problem in phylogeny
 D. FernándezBaca, J. Lagergren
 ISAAC96, pages 6574, LNCS 1178, 1996.
 Approximability of maximum splitting of ksets and some other APXcomplete problems
 V. Kann, J. Lagergren, A. Panconesi
 IPL, 58:105110, 1996.
 NADA report TRITANA9512, 1995.

Postscript.
 Strong lower bounds on the approximability of some NPO PBcomplete maximization problem
 V. Kann
 MFCS 95, pages 227236, LNCS 969, 1995.
 NADA report TRITANA9501, 1995.

Postscript.
 Polynomially bounded minimization problems that are hard to approximate
 V. Kann
 Nordic Journal of Computing 1:317331, 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:181210, 1995.
 STACS 94, LNCS 775, 1994.
 NADA report TRITANA9313, 1993.

Postscript.
 On the approximability of some NPhard minimization problems for linear systems
 E. Amaldi, V. Kann
 ECCC report TR96015, 1996
 International Symposium on Mathematical Programming, Ann Arbor, 1996
 Tech. report 957, 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>