Approximating maximum satisfiable subsystems of linear equations of bounded width

Zeev Nutov; Daniel Reichman

doi:10.1016/j.ipl.2007.11.011

Approximating maximum satisfiable subsystems of linear equations of bounded width

Zeev Nutov
, Daniel Reichman

מדעי המחשב

نتاج البحث: نشر في مجلة › مقالة › مراجعة النظراء

ملخص

We consider the problem known as MAX - SATISFY: given a system of m linear equations over the rationals, find a maximum set of equations that can be satisfied. Let r be the width of the system, that is, the maximum number of variables in an equation. We give an Ω (m^{- 1 + 1 / r})-approximation algorithm for any fixed r. Previously the best approximation ratio for this problem was Ω ((log m) / m) even for r = 2. In addition, we slightly improve the hardness results for MAX - SATISFY.

اللغة الأصلية	الإنجليزيّة
الصفحات (من إلى)	203-207
عدد الصفحات	5
دورية	Information Processing Letters
مستوى الصوت	106
رقم الإصدار	5
المعرِّفات الرقمية للأشياء	https://doi.org/10.1016/j.ipl.2007.11.011
حالة النشر	نُشِر - 31 مايو 2008

الوصول إلى المستند

10.1016/j.ipl.2007.11.011

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@article{6dad261fdfcc404c8bd2c1a304e2395d,

title = "Approximating maximum satisfiable subsystems of linear equations of bounded width",

abstract = "We consider the problem known as MAX - SATISFY: given a system of m linear equations over the rationals, find a maximum set of equations that can be satisfied. Let r be the width of the system, that is, the maximum number of variables in an equation. We give an Ω (m- 1 + 1 / r)-approximation algorithm for any fixed r. Previously the best approximation ratio for this problem was Ω ((log m) / m) even for r = 2. In addition, we slightly improve the hardness results for MAX - SATISFY.",

keywords = "Approximation algorithms, Linear equations, Satisfiable systems",

author = "Zeev Nutov and Daniel Reichman",

year = "2008",

month = may,

day = "31",

doi = "10.1016/j.ipl.2007.11.011",

language = "אנגלית",

volume = "106",

pages = "203--207",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier BV",

number = "5",

}

TY - JOUR

T1 - Approximating maximum satisfiable subsystems of linear equations of bounded width

AU - Nutov, Zeev

AU - Reichman, Daniel

PY - 2008/5/31

Y1 - 2008/5/31

N2 - We consider the problem known as MAX - SATISFY: given a system of m linear equations over the rationals, find a maximum set of equations that can be satisfied. Let r be the width of the system, that is, the maximum number of variables in an equation. We give an Ω (m- 1 + 1 / r)-approximation algorithm for any fixed r. Previously the best approximation ratio for this problem was Ω ((log m) / m) even for r = 2. In addition, we slightly improve the hardness results for MAX - SATISFY.

AB - We consider the problem known as MAX - SATISFY: given a system of m linear equations over the rationals, find a maximum set of equations that can be satisfied. Let r be the width of the system, that is, the maximum number of variables in an equation. We give an Ω (m- 1 + 1 / r)-approximation algorithm for any fixed r. Previously the best approximation ratio for this problem was Ω ((log m) / m) even for r = 2. In addition, we slightly improve the hardness results for MAX - SATISFY.

KW - Approximation algorithms

KW - Linear equations

KW - Satisfiable systems

UR - https://www.scopus.com/pages/publications/41549163566

U2 - 10.1016/j.ipl.2007.11.011

DO - 10.1016/j.ipl.2007.11.011

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:41549163566

SN - 0020-0190

VL - 106

SP - 203

EP - 207

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Approximating maximum satisfiable subsystems of linear equations of bounded width

ملخص

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا