Change search
ReferencesLink to record
Permanent link

Direct link
A new way of using semidefinite programming with applications to linear equations mod p
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
2001 (English)In: Journal of Algorithms, ISSN 0196-6774, E-ISSN 1090-2678, Vol. 39, no 2, 162-204 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2001. Vol. 39, no 2, 162-204 p.
Keyword [en]
approximation algorithms, linear equations, lower bounds, NP-hard optimization problems, semidefinite programming, improved approximation algorithms, cut
URN: urn:nbn:se:kth:diva-20556ISI: 000168309000003OAI: diva2:339252
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Journal of Algorithms

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 31 hits
ReferencesLink to record
Permanent link

Direct link