# Tag Info

21

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

An upper bound on the maximum number of stable matchings for a Stable Marriage instance is given in my Master's thesis and it is extended to the Stable Roommates problem as well.The bound is of magnitude $O(n!/2^n)$ and it can be shown that it is actually of magnitude $O\left((n!)^\frac{2}{3}\right)$. The document is thesis number 97 on page http://mpla....

17

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

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

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

15

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

15

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

8

Your problem is the multiple knapsack problem. Although I am not familiar with this problem, I believe you'll find some papers on your problem, since there are many papers on this problem (see for example a SODA 2009 paper)

7

The self-adjusting linked lists described by Bentley have practical applications in data compression. For example, bzip2 uses move-to-front encoding (among many other tricks). See also this paper by Bentley et al.

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

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

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

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

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

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

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

I can think of two situations where a linked list based linear search with heuristics may be better than using a hash table: 1. For small lists the overhead associated with calculating the hash function may matter more than the improvement in complexity. 2. You need a large enough table to avoid collisions (number of buckets should be at least twice the ...

3

Decentralized algorithms for variants of this problem have been published in A distributed and privacy preserving algorithm for identifying information hubs in social networks and Social Influence Analysis in Large-scale Networks.

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

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