Zapiski Nauchnykh Seminarov POMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zapiski Nauchnykh Seminarov POMI, 2004, Volume 316, Pages 111–128 (Mi znsl728)  

This article is cited in 11 scientific papers (total in 11 papers)

Automated proofs of upper bounds on the running time of splitting algorithms

A. S. Kulikov, S. S. Fedin

Saint-Petersburg State University
References:
Abstract: The splitting method is one of the most powerful and well-studied approaches for solving various NP-hard problems. The main idea of this method is to split an input instance of a problem into several simpler instances (further simplified by certain simplification rules), such that when the solution for each of them is found, one can construct the solution for the initial instance in polynomial time. There exists a huge number of articles describing algorithms of this type and usually a considerable part of such an article is devoted to case analysis. In this paper, we present a program that, given a set of simplification rules, automatically generates a proof of an upper bound on the running time of a splitting algorithm using these rules. As an example we report the results of experiments with such a program for the SAT, MAXSAT, and $(n,3)$-MAXSAT (the MAXSAT problem for the case where every variable in the formula appears at most three times) problems.
Received: 11.10.2004
English version:
Journal of Mathematical Sciences (New York), 2006, Volume 134, Issue 5, Pages 2383–2391
DOI: https://doi.org/10.1007/s10958-006-0114-x
Bibliographic databases:
UDC: 510.52+519.16+510.633
Language: Russian
Citation: A. S. Kulikov, S. S. Fedin, “Automated proofs of upper bounds on the running time of splitting algorithms”, Computational complexity theory. Part IX, Zap. Nauchn. Sem. POMI, 316, POMI, St. Petersburg, 2004, 111–128; J. Math. Sci. (N. Y.), 134:5 (2006), 2383–2391
Citation in format AMSBIB
\Bibitem{KulFed04}
\by A.~S.~Kulikov, S.~S.~Fedin
\paper Automated proofs of upper bounds on the running time of splitting algorithms
\inbook Computational complexity theory. Part~IX
\serial Zap. Nauchn. Sem. POMI
\yr 2004
\vol 316
\pages 111--128
\publ POMI
\publaddr St.~Petersburg
\mathnet{http://mi.mathnet.ru/znsl728}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2113060}
\zmath{https://zbmath.org/?q=an:1136.68629}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2006
\vol 134
\issue 5
\pages 2383--2391
\crossref{https://doi.org/10.1007/s10958-006-0114-x}
Linking options:
  • https://www.mathnet.ru/eng/znsl728
  • https://www.mathnet.ru/eng/znsl/v316/p111
  • This publication is cited in the following 11 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:271
    Full-text PDF :81
    References:48
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024