Sökning: onr:"swepub:oai:DiVA.org:kth-20556" >
A new way of using ...
A new way of using semidefinite programming with applications to linear equations mod p
-
Andersson, G. (författare)
-
Engebretsen, L. (författare)
-
- Håstad, Johan (författare)
- KTH,Numerisk analys och datalogi, NADA
-
(creator_code:org_t)
- Elsevier BV, 2001
- 2001
- Engelska.
-
Ingår i: Journal of Algorithms. - : Elsevier BV. - 0196-6774 .- 1090-2678. ; 39:2, s. 162-204
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- We introduce a new method of constructing approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 - kappa (p))p, where kappa (p)> 0 for all p. Using standard techniques we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p.
Nyckelord
- approximation algorithms
- linear equations
- lower bounds
- NP-hard optimization problems
- semidefinite programming
- improved approximation algorithms
- cut
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas