✦ LIBER ✦

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p

✍ Scribed by Gunnar Andersson; Lars Engebretsen; Johan Håstad

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 249 KB
Volume: 39
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1154

No coin nor oath required. For personal study only.

✦ Synopsis

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 y p p, where 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.

📜 SIMILAR VOLUMES

A Concise Pharmachology of the more Impo

A Concise Pharmachology of the more Important Drugs, Together with an outline of their Therapeutic Applications and Introduction to the Art of Prescribing, by F. G. Hobart, Ph.C., member of the pharmaceutical Society, head of the Pharmaceutical Department, Westminister Hospital, lecturer in Pharmaceutics, Westminster Hospital, School of Medicine, member of the B. T. Codex, “Action and Uses” Sub-Committee and of the pharmacy Sub-Committee, 1934, and G. Melton, M.D., M.R.C.P.-sometime Medical Registrar, Westminster Hospital School of Medicine. 170 pages. Distributed by the Chemical Publishing Co., Inc., 148 LaFayette St., New York city. Price, $3.00

📂 Article 📅 1938 🏛 Elsevier ⚖ 199 KB