Approximating minimum unsatisfiability of linear equations

Piotr Berman; Marek Karpinski

Approximating minimum unsatisfiability of linear equations

Piotr Berman, Marek Karpinski

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the minimized objective function is the number of equations that are not satisfied. For the case of the finite field GF[2], this problem is also known as the Nearest Codeword problem. In this note we show that for any constant c there exists a randomized polynomial time algorithm that approximates the above problem, called the Minimum Unsatisfiability of Linear Equations (Min-Unsatisfy for short), with n/(clogn) approximation ratio. Our results hold for any field in which systems of linear equations can be solved in polynomial time.

Original language	English (US)
Title of host publication	Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Publisher	Association for Computing Machinery
Pages	514-516
Number of pages	3
ISBN (Electronic)	089871513X
State	Published - 2002
Event	13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States Duration: Jan 6 2002 → Jan 8 2002

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	06-08-January-2002

Other

Other	13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country/Territory	United States
City	San Francisco
Period	1/6/02 → 1/8/02

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Cite this

@inproceedings{8017757a35f34224bd0c3db13f39ba12,

title = "Approximating minimum unsatisfiability of linear equations",

abstract = "We consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the minimized objective function is the number of equations that are not satisfied. For the case of the finite field GF[2], this problem is also known as the Nearest Codeword problem. In this note we show that for any constant c there exists a randomized polynomial time algorithm that approximates the above problem, called the Minimum Unsatisfiability of Linear Equations (Min-Unsatisfy for short), with n/(clogn) approximation ratio. Our results hold for any field in which systems of linear equations can be solved in polynomial time.",

author = "Piotr Berman and Marek Karpinski",

year = "2002",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "514--516",

booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002",

note = "13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 ; Conference date: 06-01-2002 Through 08-01-2002",

}

Berman, P & Karpinski, M 2002, Approximating minimum unsatisfiability of linear equations. in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 06-08-January-2002, Association for Computing Machinery, pp. 514-516, 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, San Francisco, United States, 1/6/02.

Approximating minimum unsatisfiability of linear equations. / Berman, Piotr; Karpinski, Marek.
Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Association for Computing Machinery, 2002. p. 514-516 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 06-08-January-2002).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximating minimum unsatisfiability of linear equations

AU - Berman, Piotr

AU - Karpinski, Marek

PY - 2002

Y1 - 2002

N2 - We consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the minimized objective function is the number of equations that are not satisfied. For the case of the finite field GF[2], this problem is also known as the Nearest Codeword problem. In this note we show that for any constant c there exists a randomized polynomial time algorithm that approximates the above problem, called the Minimum Unsatisfiability of Linear Equations (Min-Unsatisfy for short), with n/(clogn) approximation ratio. Our results hold for any field in which systems of linear equations can be solved in polynomial time.

AB - We consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the minimized objective function is the number of equations that are not satisfied. For the case of the finite field GF[2], this problem is also known as the Nearest Codeword problem. In this note we show that for any constant c there exists a randomized polynomial time algorithm that approximates the above problem, called the Minimum Unsatisfiability of Linear Equations (Min-Unsatisfy for short), with n/(clogn) approximation ratio. Our results hold for any field in which systems of linear equations can be solved in polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=84968835314&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84968835314&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84968835314

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 514

EP - 516

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -

Approximating minimum unsatisfiability of linear equations

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this