# Tag Info

23

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 ...

19

As far as I know, the state of the art is what is reported in Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos (2012), "On exact algorithms for treewidth", ACM Transactions on Algorithms 9 (1): A12, doi:10.1145/2390176.2390188. The methods described there include an implemented $O^*(2^n)$ algorithm with ...

18

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 ...

17

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 ...

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 ...

16

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

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 ...

14

No, the NN heuristic does not have constant factor for metric TSP. Rosenkrantz, Stearns, and Lewis proved in An Analysis of Several Heuristics for the Traveling Salesman Problem. SIAM J. Comput. 6(3): 563-581 (1977) that the worst case ratio of the tour obtained by the nearest neighbor method is bounded above by a logarithmic function of the number of ...

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 ...

10

I wrote a paper called A Fast Parallel Branch and Bound Algorithm for Treewidth, in ICTAI 2011. It can compute treewidth in multi-core. I used lots of heuristics and spent lots of time refining the program. I was a random undergraduate student in China and didn't make it to a good conference. But based on my experiment results, I think my program is very ...

8

It is equivalent to ask, among a set of $d$ non-negatively weighted items, for the $d+1$ subsets of minimum total weight. One can form all the subsets of the items into a tree, in which the parent of a subset is formed by removing its heaviest item (with ties broken arbitrarily but consistently); the $d+1$ solutions will form a subtree of this tree connected ...

8

Time $O(d^3\log d)$ lemma: Fix any $x\in[0,1]^d$. Then there is a set $S$ containing $d+1$ corners of $\{0,1\}^d$ that are closest to $x$ and such that $S$ is connected (meaning that the subgraph of the hypercube induced by $S$ is connected). Proof. First consider the case that $x$ has no coordinates equal to $1/2$. Given any corner $a$ in $S$, flipping ...

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.

6

One general approach to generating harder instances is as follows: Start with a random problem instance. Embed a "hidden backdoor": randomly choose a good solution (one that's likely to be much better than any solution that already exists) and modify the problem instance to forcibly embed this solution into the problem instance. For instance, for TSP, you ...

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-...

5

Here http://arxiv.org/abs/1304.6321 (accepted at FOCS this year) Bodlaender et al. give an $O^*(2^k)$ algorithm that gives a tree-decomposition of width at most 5k+4 if the graph has tree-width at most k. May be it can interest you.

5

Here are two surveys on algorithms for calculating treewidth that may be helpful. The first one has empirical comparisons, and it has miscellaneous algorithms implemented as a Java library. treewidth.com / Computing treewidth with Libtw Dijk, Heuvel, Slob There are many algorithms to compute an upperbound, a lowerbound or the exact treewidth of a graph. ...

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 ...

4

This seems like a hard problem. You might be able to do something if the rectangles have some packing property. For example, if no point is covered more than $t$ times (for some constant T), and the rectangles are not too long and narrow. Then one can probably prove that a curve intersects $O( \sqrt{n})$ rectangles, using some $k$-ply planar separator ...

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

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

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.

3

Sage doesn't know how to compute treewidth exactly but it can give you the pathwidth of small graphs. http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/vertex_separation.html I would be verrryyyyyyyy glad to learn that there is anything implemented and public to compute tree-decompositions, though :-) Nathann

3

By simplification I understand either minimization or determinization. I'll try to sum up what I know about both problems, in the quite general setting of weighted automata over arbitrary semiring. The original works were done by Marcel-Paul Schützenberger (who introduced them), and you'll find a nice account of what is known about them in the book Elements ...

3

an approach that often gives you high control over the nature of solutions is conversion from one NP complete problem to another. now you define "interesting" in your question in a statistical way, but another neat approach is to use classic problems from the field. my favorite is factoring/SAT. it is trivial to find either "smooth" numbers with lots of ...

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 ...

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 ...

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