Standard

A new approach to proving upper bounds for MAX-2-SAT. / Kojevnikov, Arist; Kulikov, Alexander S.

2006. 11-17 Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States.

Research output: Contribution to conference › Paper › peer-review

Harvard

Kojevnikov, A & Kulikov, AS 2006, 'A new approach to proving upper bounds for MAX-2-SAT', Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States, 22/01/06 - 24/01/06 pp. 11-17.

APA

Kojevnikov, A., & Kulikov, A. S. (2006). A new approach to proving upper bounds for MAX-2-SAT. 11-17. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States.

Vancouver

Kojevnikov A, Kulikov AS. A new approach to proving upper bounds for MAX-2-SAT. 2006. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States.

Author

Kojevnikov, Arist ; Kulikov, Alexander S. / A new approach to proving upper bounds for MAX-2-SAT. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States.7 p.

BibTeX

@conference{d278802a186c4369be5800895b8a770e,
title = "A new approach to proving upper bounds for MAX-2-SAT",
abstract = "In this paper we present a new approach to proving upper bounds for the maximum 2-satisfiability problem (MAX-2-SAT). We present a new 2 K/5.5-time algorithm for MAX-2-SAT, where K is the number of clauses in an input formula. We also obtain a 2N/6 bound, where N is the number of variables in an input formula, for a particular case of MAX-2-SAT, where each variable appears in at most three 2-clauses. This immediately implies a 2N/6 bound, where N is the number of vertices in an input graph, for the independent set problem on 3-regular graphs. The key point of our improvement is a combined complexity measure for estimating the running time of an algorithm. By using a new complexity measure we are able to provide a much simpler proof of new upper bounds for MAX-2-SAT than proofs of previously known bounds.",
author = "Arist Kojevnikov and Kulikov, {Alexander S.}",
year = "2006",
month = feb,
day = "28",
language = "English",
pages = "11--17",
note = "Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 22-01-2006 Through 24-01-2006",

}

RIS

TY - CONF

T1 - A new approach to proving upper bounds for MAX-2-SAT

AU - Kojevnikov, Arist

AU - Kulikov, Alexander S.

PY - 2006/2/28

Y1 - 2006/2/28

N2 - In this paper we present a new approach to proving upper bounds for the maximum 2-satisfiability problem (MAX-2-SAT). We present a new 2 K/5.5-time algorithm for MAX-2-SAT, where K is the number of clauses in an input formula. We also obtain a 2N/6 bound, where N is the number of variables in an input formula, for a particular case of MAX-2-SAT, where each variable appears in at most three 2-clauses. This immediately implies a 2N/6 bound, where N is the number of vertices in an input graph, for the independent set problem on 3-regular graphs. The key point of our improvement is a combined complexity measure for estimating the running time of an algorithm. By using a new complexity measure we are able to provide a much simpler proof of new upper bounds for MAX-2-SAT than proofs of previously known bounds.

AB - In this paper we present a new approach to proving upper bounds for the maximum 2-satisfiability problem (MAX-2-SAT). We present a new 2 K/5.5-time algorithm for MAX-2-SAT, where K is the number of clauses in an input formula. We also obtain a 2N/6 bound, where N is the number of variables in an input formula, for a particular case of MAX-2-SAT, where each variable appears in at most three 2-clauses. This immediately implies a 2N/6 bound, where N is the number of vertices in an input graph, for the independent set problem on 3-regular graphs. The key point of our improvement is a combined complexity measure for estimating the running time of an algorithm. By using a new complexity measure we are able to provide a much simpler proof of new upper bounds for MAX-2-SAT than proofs of previously known bounds.

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

M3 - Paper

AN - SCOPUS:33244473449

SP - 11

EP - 17

T2 - Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 22 January 2006 through 24 January 2006

ER -

ID: 49824919