A new way of using semidefinite programming with applications to linear equations mod p

Citation
G. Andersson et al., A new way of using semidefinite programming with applications to linear equations mod p, J ALGORITHM, 39(2), 2001, pp. 162-204
Citations number
10
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF ALGORITHMS
ISSN journal
01966774 → ACNP
Volume
39
Issue
2
Year of publication
2001
Pages
162 - 204
Database
ISI
SICI code
0196-6774(200105)39:2<162:ANWOUS>2.0.ZU;2-Y
Abstract
We introduce a new method of constructing approximation algorithms for comb inatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a const ellation of vectors in the semidefinite program. When we apply this techniq ue 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 t hat it is NP-hard to approximate the problem within a constant ratio, indep endent of p. (C) 2001 Academic Press.