Monday, 27. March 2017

KTH Research Projec...

KTH Research Project Database > Computer Science & Information Technology

Computer Science &...

Cognitive Science

Communication Science

Computer and System Science

Computer Science Education

Integrated Devices and Circuits

Parallel and distributed computing


»Research Fields

»Organisational Structure


Approximation algorithms (»Add to Infobox)

Research Leader: Professor Johan Håstad
Professor Viggo Kann

Theoretical Computer Science

There are many hard combinatorial optimisation problems. One famous such class of problems concerns the NP-complete problems, which include colouring problems, the travelling salesman problem and integer programming. The main topic of this project is to investigate to what extent the optimum value of these problems (as well as other problems) can be approximated efficiently. These investigations are naturally divided into two types of activities, namely to prove positive and negative approximation results. To get a positive result one constructs an algorithm, proves that it is efficient and approximates the solution to a given hard problem to a given accuracy. To get negative results one usually proves that approximating a given problem remains NP-hard. Some of our recent negative results prove that it is hard to approximate the size of the largest clique, and for a linear system of Boolean/integer equations to approximate the number of equations that can be satisfied simultaneously. Some of our positive results give approximation algorithms for set splitting and linear equations mod p using semi definite programming. We have studied the problems of vertex cover, colourability of graphs of small chromatic index and constraint satisfaction problems where each constraint only depends on two variables. A current project is to understand which constraint satisfaction problems allow a nontrivial approximation algorithm.

Period: 1989-01-01

Algorithm, Approximation, NP-complete

Project URL:


European Commission


VR (The Swedish Research Council)


»Advanced Search

INFOBOX (0/0) show all
Your infobox is empty

Powered by