Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms |
| |
Authors: | Nicolas Bourgeois Vangelis Th Paschos |
| |
Institution: | a LAMSADE, CNRS and Université Paris-Dauphine, Franceb Institut Universitaire de France, France |
| |
Abstract: | Using ideas and results from polynomial time approximation and exact computation we design approximation algorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, max independent set and min vertex cover. |
| |
Keywords: | Approximation algorithms Exponential time algorithms Maximum independent set Minimum vertex cover |
本文献已被 ScienceDirect 等数据库收录! |