|
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
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
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
Linking options:
https://www.mathnet.ru/eng/znsl728 https://www.mathnet.ru/eng/znsl/v316/p111
|
Statistics & downloads: |
Abstract page: | 271 | Full-text PDF : | 81 | References: | 48 |
|