Standard

MAX SAT approximation beyond the limits of polynomial-time approximation. / Dantsin, Evgeny; Gavrilovich, Michael; Hirsch, Edward A.; Konev, Boris.

в: Annals of Pure and Applied Logic, Том 113, № 1-3, 27.12.2001, стр. 81-94.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Dantsin, E, Gavrilovich, M, Hirsch, EA & Konev, B 2001, 'MAX SAT approximation beyond the limits of polynomial-time approximation', Annals of Pure and Applied Logic, Том. 113, № 1-3, стр. 81-94. https://doi.org/10.1016/S0168-0072(01)00052-5

APA

Dantsin, E., Gavrilovich, M., Hirsch, E. A., & Konev, B. (2001). MAX SAT approximation beyond the limits of polynomial-time approximation. Annals of Pure and Applied Logic, 113(1-3), 81-94. https://doi.org/10.1016/S0168-0072(01)00052-5

Vancouver

Dantsin E, Gavrilovich M, Hirsch EA, Konev B. MAX SAT approximation beyond the limits of polynomial-time approximation. Annals of Pure and Applied Logic. 2001 Дек. 27;113(1-3):81-94. https://doi.org/10.1016/S0168-0072(01)00052-5

Author

Dantsin, Evgeny ; Gavrilovich, Michael ; Hirsch, Edward A. ; Konev, Boris. / MAX SAT approximation beyond the limits of polynomial-time approximation. в: Annals of Pure and Applied Logic. 2001 ; Том 113, № 1-3. стр. 81-94.

BibTeX

@article{d9afbe3ed85e4cbfae24c84c3189e1d4,
title = "MAX SAT approximation beyond the limits of polynomial-time approximation",
abstract = "We describe approximation algorithms for (unweighted) MAX SAT with performance ratios arbitrarily close to 1, in particular, when performance ratios exceed the limits of polynomial-time approximation. Namely, given a polynomial-time α-approximation algorithm A0, we construct an (α+ε)-approximation algorithm A. The algorithm A runs in time of the order cεk, where k is the number of clauses in the input formula and c is a constant depending on α. Thus we estimate the cost of improving a performance ratio. Similar constructions for MAX 2SAT and MAX 3SAT are also described. Taking known algorithms as A0 (for example, the Karloff-Zwick algorithm for MAX 3SAT), we obtain particular upper bounds on the running time of A.",
keywords = "03B05, 03B25, 68W25, Approximation algorithms, Maximum satisfiability problem",
author = "Evgeny Dantsin and Michael Gavrilovich and Hirsch, {Edward A.} and Boris Konev",
year = "2001",
month = dec,
day = "27",
doi = "10.1016/S0168-0072(01)00052-5",
language = "English",
volume = "113",
pages = "81--94",
journal = "Annals of Pure and Applied Logic",
issn = "0168-0072",
publisher = "Elsevier",
number = "1-3",

}

RIS

TY - JOUR

T1 - MAX SAT approximation beyond the limits of polynomial-time approximation

AU - Dantsin, Evgeny

AU - Gavrilovich, Michael

AU - Hirsch, Edward A.

AU - Konev, Boris

PY - 2001/12/27

Y1 - 2001/12/27

N2 - We describe approximation algorithms for (unweighted) MAX SAT with performance ratios arbitrarily close to 1, in particular, when performance ratios exceed the limits of polynomial-time approximation. Namely, given a polynomial-time α-approximation algorithm A0, we construct an (α+ε)-approximation algorithm A. The algorithm A runs in time of the order cεk, where k is the number of clauses in the input formula and c is a constant depending on α. Thus we estimate the cost of improving a performance ratio. Similar constructions for MAX 2SAT and MAX 3SAT are also described. Taking known algorithms as A0 (for example, the Karloff-Zwick algorithm for MAX 3SAT), we obtain particular upper bounds on the running time of A.

AB - We describe approximation algorithms for (unweighted) MAX SAT with performance ratios arbitrarily close to 1, in particular, when performance ratios exceed the limits of polynomial-time approximation. Namely, given a polynomial-time α-approximation algorithm A0, we construct an (α+ε)-approximation algorithm A. The algorithm A runs in time of the order cεk, where k is the number of clauses in the input formula and c is a constant depending on α. Thus we estimate the cost of improving a performance ratio. Similar constructions for MAX 2SAT and MAX 3SAT are also described. Taking known algorithms as A0 (for example, the Karloff-Zwick algorithm for MAX 3SAT), we obtain particular upper bounds on the running time of A.

KW - 03B05

KW - 03B25

KW - 68W25

KW - Approximation algorithms

KW - Maximum satisfiability problem

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

U2 - 10.1016/S0168-0072(01)00052-5

DO - 10.1016/S0168-0072(01)00052-5

M3 - Article

AN - SCOPUS:0035960967

VL - 113

SP - 81

EP - 94

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

SN - 0168-0072

IS - 1-3

ER -

ID: 49829486