Wednesday, 26. April 2017

KTH Research Projec...

KTH Research Project Database > Computer Science & Information Technology

Computer Science &...
PROJECT




Cognitive Science


Communication Science


Computer and System Science


Computer Science Education


Integrated Devices and Circuits


Parallel and distributed computing


OVERVIEWS

»Research Fields

»Organisational Structure

»Persons



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

Keywords:
Algorithm, Approximation, NP-complete

Project URL:
http://www.nada.kth.se/theory/projects/approx.html

SOURCE OF FUNDING (3/3) 

European Commission

KTH

VR (The Swedish Research Council)


SEARCH



»Advanced Search



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




Powered by AVERISinfo@avedas.com