



There are many hard combinatorial optimisation problems. One famous such class of problems concerns the NPcomplete 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 NPhard. 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: 19890101
Keywords:
Algorithm, Approximation, NPcomplete
Project URL:
http://www.nada.kth.se/theory/projects/approx.html

SOURCE OF FUNDING (3/3) 

European Commission
KTH
VR (The Swedish Research Council)



