# Tag Info

27

I am assuming that you are referring to CDCL SAT solvers on benchmark data sets like those used in the SAT Competition. These programs are based on many heuristics and lots of optimization. There were some very good introductions to how they work at Theoretical Foundations of Applied SAT Solving workshop at Banff in 2014 (videos). These algorithms are based ...

22

I am typing this quite quickly due to severe time constraints (and didn't even get to responding earlier for the same reason), but I thought I would try to at least chip in with my two cents. I think this is a truly great question, and have spent a nontrivial amount of time over the last few years looking into this. (Full disclosure: I have received a big ...

18

Let me add my two cents of understanding to this, even though I've never actually worked in the area. You're asking one of two questions, "what are all the known approaches to proving theoretical efficiency of some SAT solver for some type of instances" and "why are SAT solvers efficient in reality". For the former question, I'll just direct you to the ...

18

I'm not an expert in this area, but I think the random SAT / phase transition stuff is more or less completely unrelated to the industrial/practical applications stuff. E.g., the very good solvers for random instances (such as https://www.gableske.net/dimetheus) are based on the statistical physics methods (belief propagation etc.) I believe, whereas the ...

17

There is a paper "Relating Proof Complexity Measures and Practical Hardness of SAT" by Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný in CP '12 that attempts to link the hardness or easiness of solving certain formulas by CDCL solvers with resolution proof complexity measures, in particular resolution proof space. The results are ...

16

See Josh Grochow's answer to Poly time superset of NP complete language with infinitely many strings excluded from it. According to that answer, under some natural cryptographic assumptions, for every co-NP-complete problem there is an infinite subset $\Phi$ of instances such that membership in $\Phi$ is polynomial time, and the decision problem restricted ...

12

I hope this partly answers your question: Most known heuristics like Greedy, Naerest Neighbor, Lin-Kerninhan etc. perfrom quite well for (symmetric) TSP without triangle inequality. You may check these heuristics with the Concorde TSP Solver which is the best TSP solver I know so far. In theory, there is no heuristic for TSP without triangle inequality ...

7

An exponential upper bound has been given in Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings.

5

MaxSAT - people actually care about this because SAT solvers are so well-developed that often the best route for your favorite NP optimization problem in practice is to reduce it to MaxSAT and then apply one of the well-known solvers. Check out the SAT competition for benchmarks etc. Clique-finders get used in computational biology and combinatorics, and ...

5

There are known pre-processing methods that rely solely on the graph representation itself (and not on any kind of geometric embedding) to establish good heuristics for A*. Perhaps the most well-known example in recent research is called ALT (A* + Landmarks + Triangle-Inequality). Here is one of the original papers on this topic: https://www.microsoft.com/en-...

4

You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities). http://www.sciencedirect.com/science/article/pii/0167637783900482 http://www.sciencedirect.com/science/article/pii/0167637786900817

3

Define a language $L$ to be nicely-ordered if $L \subseteq a^*b^*c^*d^*\cdots$, i.e., in every word of $L$, the letters appear solely in lexicographic order. Conjecture: the optimum is always obtained by some nicely-ordered language, i.e., if $G$ is the smallest such grammar that generates $S$, then there exists a grammar $G'$ of the same size that also ...

3

The short answer is no, we don't understand it. The long answer is yes, we have some bounds, but those bounds aren't very helpful. It's quite clear that the worst-case running time is exponential. That's not very helpful, because we know that in some/many practical situations, it seems to run fairly rapidly -- and we don't really know why. We don't know ...

3

While there are many heuristics (arguably all of them) that take exponential time in the worst-case, what usually makes them attractive (and marketable) is that they "appear" to perform much better in practice, and in fact it's hard to find examples where they are provably exponential. Two canonical examples are the simplex algorithm for linear programming ...

3

There is no algorithm that runs in time $o(n^2)$ on an $n$-point metric space and returns a tour with weight within a constant factor of the minimum weight: see the argument in Section 9 of this paper by Indyk. On the other hand, if you just want an approximation to the weight of the optimal tour, without actually getting a tour, then you can use this ...

3

This problem is known as Weighted Set Packing and it is NP-complete. In order to see this, assign each customer a set with weight which equals the sum of the item values he asks for. The best known approximation algorithm for this problem gives a $\sqrt |\cal U|$-approximation for the optimal solution.

2

Besides basic Kerninghan-Lin algorithm (complexity $O(n^2 log(n))$), there's also Fiduccia-Mattheyses (1982) heuristic, which is a variant of Kerninghan-Lin with linear complexity $O(E)$, where $E$ is number of edges. It also starts with a random bisection and iteratively improves it by swapping the nodes from one partition to the other. In contrast to K-L, ...

2

Note that in optimization, "convergence rate" usually means asymptotic behavior. That is, the rate only applies to the neighborhood of optimal solutions. In that sense, Luo & Tseng did prove linear convergence rates for some non-strongly convex objective functions in the paper "On the convergence of the coordinate descent method for convex differentiable ...

2

In general, finding least-cost paths with arbitrary time-dependent edge costs is NP-hard, assuming that either (a) waiting at nodes is forbidden and your costs are not FIFO-preserving (e.g., see here for brief discussion on this complexity, as well as others: https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf) or (b) the cost you are trying to optimize is not ...

2

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows. Let $c=(\sqrt{17}-1)/2 \approx 1.56$. There are three objects of size $c$, $1$, and $1$. There are two bins of size $2$ and $c$. Initially $a=1$. Some heuristics will place the largest object into the big bin, necessitating $a$ increasing from 1 to at ...

2

You'd have to tweak the limits (in particular max_level may be too low), but for at least some "real" problems this is within the bounds of Knuth's algorithm M. See also The documentation of algorithm D, which describes the basic file format; the documentation of algorithm M just explains the changes made to generalise it; the latest preprint of fascicle ...

1

It depends on the precise model of computation you work within. However, this doesn't seem to be a useful direction for proving lower bounds on the time to factor. Uniform algorithms Let's look at uniform algorithms. Suppose our model of computation is a Turing machine or the transdichotomous model or something similar, where each step can do at most a ...

1

Operations research have a plenty of combinatorial optimization problems where the development of heuristics for minimization (or maximization) of resulting costs are an very active area. For example, vehicle routing problem, capacitated arc routing problem, minimum spanning tree problems and variations of these problems.

1

Since the original question title asks for theoretical explanations, let me point to a paper that might provide a kind of non-standard theoretical explanation. The main result of the paper is that one can design a polynomial time errorless heuristic with exponentially small failure rate for all paddable languages (including SAT), if the errors are counted by ...

1

Because the order of your symbols does not matter, you can always move the nonterminals to the very right of the productions. If there is no more than one in any rule, the resulting grammar is regular. If there are several, I think they can easily be coded into a single one. Thus you can look for the minimal regular grammar, and this problem is quite well-...

1

This seems similar to bin-packing problem. I set $a=1$ and try to solve the bin-packing problem of putting objects of size $O_1$ to $O_n$. If I cannot find the solution then I increase $a$ with value $\delta >0$ and try again. If it doesn't work I increase $a$ by $2\delta$ and so on.

1

Your problem is called maximum weighted simple b-matching, and it's solvable in strongly polynomial time. See this paper for instance.

1

SAT-solvers are another common class of heuristics. There are many and of course they take exponential time in the worst case. My suggestion is to explain to the reviewers that the problem is NP-complete and cannot be solved or approximated in less than exponential time if there are such results. That should suffice if your algorithm outperforms the best ...

1

Best one I know is the polytime approximation algorithm of Asadpour et al., although maybe this isn't what you want (i.e. you want exact solution, I'm guessing). Anyway, the algorithm achieves $O(\log n / \log \log n)$ approximation for $n$-vertex graphs.

1

Appreciable literature is available in this standard book on Approximation Algo by Vazirani http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf Refer to chapter 10 for details.

Only top voted, non community-wiki answers of a minimum length are eligible