Worst-case study of local search for MAX-k-SAT

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

16 Цитирования (Scopus)


During the past 3 years there was a considerable growth in the number of algorithms solving MAX-SAT and MAX-2-SAT in worst-case time of the order c K, where c<2 is a constant, and K is the number of clauses of the input formula. However, similar bounds w.r.t. the number of variables instead of the number of clauses are not known. Also, it was proved that approximate solutions for these problems (even beyond inapproximability ratios) can be obtained faster than exact solutions. However, the corresponding exponents still depended on the number of clauses of the input formula. In this paper, we give a randomized (1-ε)-approximation algorithm for MAX-k-SAT whose worst-case time bound depends on the number of variables. Our algorithm and its analysis are based on Schöning's proof of the best current worst-case time bound for k-SAT (in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, FOCS'99, 1999 pp. 410-414). Similarly to Schöning's algorithm (which is also very close to Papadimitriou's algorithm (in: Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, FOCS'91, 1991, pp. 163-169) and the experimentally successful WalkSAT family by Selman et al. (in: Proceedings of the AAAI'97, 1997, pp. 321-326; in: Proceedings of the 12th National Conference on Artificial Intelligence, AAAI'94, 1994, pp. 337-343)), our algorithm makes random walks of polynomial length. We prove that the probability of error in each walk is at most 1 - ck,ε-N, where N is the number of variables, and ck,ε < 2 is a constant depending on k and ε. Therefore, making ⌈-ln ρ⌉ck,εN such walks gives the probability of error bounded from above by any predefined constant ρ > 0.

Язык оригиналаанглийский
Страницы (с-по)173-184
Число страниц12
ЖурналDiscrete Applied Mathematics
Номер выпуска2
СостояниеОпубликовано - 15 авг 2003
СобытиеCMMSE 2002 - Alicante, Испания
Продолжительность: 20 сен 200225 сен 2002

Предметные области Scopus

  • Дискретная математика и комбинаторика
  • Прикладная математика


Подробные сведения о темах исследования «Worst-case study of local search for MAX-k-SAT». Вместе они формируют уникальный семантический отпечаток (fingerprint).