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
מזהי עצם דיגיטלי (DOIs)	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

תקציר

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי