52
I've studied the problem and I found the best known algorithms for TSP.
$n$ is the number of vertices, $M$ is the maximal edge weight.
All bounds are given up to a polynomial factor of the input size ($poly(n, \log M)$).
We denote Asymmetric TSP by ATSP.
1. Exact Algorithms for TSP
1.1. General ATSP
$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$ time and $exp$-...
27
A 1.1-approximation can be obtained in time (and space) $O^*(1.932^n)$ by adapting a "truncated" version of Held and Karp's exact $O^*(2^n)$ algorithm. Here $n$ is the number of locations. More in general, a $(1+\epsilon)$-approximation can be found in time $O^*(2^{(1-\epsilon/2)n})$ for all $\epsilon \le 2/5$. This is from:
Nicolas Boria, Nicolas Bougeois,...
26
Luca, since a year has passed, you probably have researched your own
answer. I'm answering some of your questions here just for the
record. I review some Lagrangian-relaxation algorithms for the
problems you mention, and sketch the connection to learning (in
particular, following expert advice). I don't comment here on SDP
algorithms.
Note that the ...
25
Cybenko's result is fairly intuitive, as I hope to convey below; what makes things more tricky is he was aiming both for generality, as well as a minimal number of hidden layers. Kolmogorov's result (mentioned by vzn) in fact achieves a stronger guarantee, but is somewhat less relevant to machine learning (in particular, it does not build a standard neural ...
21
I strongly disagree with the last paragraph. Blanket statements like that are not useful. If you look at papers in many systems areas such as networking, databases, AI and so on you will see that plenty of approximation algorithms are used in practice. There are some problems for which one desires very accurate answers; for example say an airline interesting ...
21
This is a special case of the Travelling Salesman with Neighborhoods (TSPN) problem. In the general version, the neighborhoods need not all be the same.
A paper by Dumitrescu and Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, addresses your question. They give a constant factor approximation algorithm for a slightly more general ...
20
As Jukka points out, computational geometry is a rich source of problems that can be solved in polynomial time, but we wish to get fast approximations. The classic "ideal" result is an "LTAS" (linear time approximation scheme) whose running time would be of the form $O(n + \text{poly}(1/\epsilon))$ - usually these are obtained by extracting a constant (poly($...
19
There is a truly awesome list of all known graph classes that have some nontrivial algorithms for MIS: see this entry in the graph classes website.
17
I presume you are talking about unconstrained minimization. Your question should specify if you are considering a specific problem structure. Otherwise, the answer is no.
First I should dispel a myth. The classical gradient descent method (also called steepest descent method) is not even guaranteed to find a local minimizer. It stops when it has found a ...
17
One example is Maximum Independent Set. It is NP-hard to approximate the problem with ratio $n^{1-\epsilon}$ (Zuckerman, 2007). However, Bourgeois et al. (2011) give a simple $n^{1/2}$-approximation algorithm with running time $O^*(2^{\sqrt{n} \log n})$. Here, $n$ denotes the number of vertices of the input graph and the $O^*$-notation hides polynomial ...
15
Non-exhaustive list of recent papers that find approximate solutions for problems in $P$
1) There is a great amount of work on approximate solutions for linear equations (symmetric diagonally dominant) in nearly linear time $\mathcal{O}(n\cdot\text{polylog}(n))$
(list of papers) http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html
(In general most ...
15
A general rule of thumb is that the more abstract/exotic the mathematics you want to mechanise, the easier it gets. Conversely, the more concrete/familiar the mathematics is, the harder it will be. So (for instance) rare animals like predicative point-free topology are vastly easier to mechanize than ordinary metric topology.
This might initially seem a ...
14
Yes, by a reduction from MaxCut to triangle-free MaxCut. Here is what Wikipedia calls an L-reduction
Given an instance $G$ of Max-Cut, construct the 3-stretch $G'$ by subdividing each edge into three edges. Then the order of the maximum cut of $G'$ is the order of the maximum cut of $G$ plus twice the number of edges in $G$. Since the size of a max ...
14
It seems to me the pseudo-polynomial time dynamic programming algorithm for Subset Sum problem also works for this problem. For each vertex $v_i$, we compute the set $L_i$ consisting of all possible values of paths ended at $v_i$. Then, we have the recurrence relation:
$L_i=\{g(v_i)\}\cup\{x+g(v_i)\mid x\in \bigcup_{j\in prec(i)} L_j\}$. Following a ...
13
A comment upgraded to partial answer:
There is quite some work these days on a conjectured (or not) quantum version of the PCP theorem: see for example this blog post by Scott Aaronson
http://www.scottaaronson.com/blog/?p=139
or this answer by Peter Shor on MathOverflow
https://mathoverflow.net/questions/45106/quantum-pcp-theorem/45167#45167
Concerning ...
13
For the constant-time task of testing graph properties, an interesting characterization is known. A graph property is a function from all graphs to $\{0,1\}$, and a graph property $P$ is testable if there is a randomized algorithm $A$ such that for all $\varepsilon > 0$ and all graphs $G$:
$A(G)$ reads only $g(\varepsilon)$ edges of $G$ for some function ...
13
There is a complete characterization of coverage functions in terms of such equations. For |X|>3 there are more equations than the ones pointed. Each of these equations can be thought as a constraint on discrete $k^{th}$ derivative.
Monotone increase function if and only if first order discrete derivative is +ve. i.e. $f(B)-f(A)\ge 0$ when $A\subseteq B$.
...
13
Complementary slackness is key in designing primal-dual algorithms. The basic idea is:
Start with a feasible dual solution $y$.
Attempt to find primal feasible $x$ such that $(x, y)$ satisfy complementary slackness.
If step 2. succeeded we are done. Otherwise an obstruction to finding $x$ gives a way to modify $y$ so that the dual objective function value ...
12
Compute a maximum matching in the complement of the input graph. Every unmatched node must be in a different color class in any coloring. So: if you get at least cn matched edges, then the matching itself gives you a coloring with an upper bound of (1-c)n, and an approximation ratio of 64(1-c). If you don't get at least cn edges, then you get a lower bound ...
12
Approximate counting is useful in complexity theory. For instance,
Jin Cai uses it to show that $S_2^p \subseteq ZPP^{NP}$, see
http://pages.cs.wisc.edu/~jyc/papers/S2-j.pdf
12
An example from the parameterized complexity is a kernelization for the vertex cover problem using a theorem of Nemhauser and Trotter.
In the minimum vertex cover problem, we are given an undirected graph G, and we need to find a vertex cover of G of minimum size. A vertex cover of an undirected graph is a vertex subset that touches all edges.
Here is an ...
12
I don't have a good overview of this problem, but I can give some examples.
A simple approximation algorithm would be to find some order of the nodes and greedily select the nodes to be in the independent set if non of its previous neighbors have been selected in the independent set.
If the graph has degeneracy $d$ then using the degeneracy ordering will ...
12
Isn't there a straightforward approximation-preserving reduction from maximum independent set (MIS) in undirected graphs to your problem?
Given undirected graph G=(V,E), form DAG A=(V,E') by ordering the vertices arbitrarily and directing the edges accordingly, then take B=(V,{}) to be the DAG with the same vertices but no edges.
Any subgraph common to A ...
11
One example is related to tree decompositions and graphs of small treewidth.
Typically, if we are given a tree decomposition, it is fairly straightforward to apply dynamic programming to solve a given graph problem $B$ optimally. The running time depends on the width of the tree decomposition.
However, usually we are not given a tree decomposition, but we ...
11
I can interpret this question in two different ways:
1) When it comes to algorithmic properties of packing problems on graphs of bounded treewidth, Courcelle's Theorem shows that for every fixed $k$ we can optimally solve problems expressible in Monadic Second Order Logic in linear time on graphs of treewidth at most $k$ (see for example http://dx.doi.org/...
11
Kellerer et al. (1997) gives with accuracy $\epsilon$ a $O(\min \{ n/ \epsilon, n + 1/ \epsilon^2 \log(1/ \epsilon) \})$ time and $O(n + 1/ \epsilon)$ space approximation scheme.
Further improving on this, Kellerer et al. (2003) gives a FPTAS with $O(\min \{n \cdot 1/ \epsilon , n + 1/ \epsilon^2 \log( 1/ \epsilon) \} )$ time and $O(n+1/ \epsilon)$ space. ...
11
I am not aware of a general theory being developed on approximation algorithms for problems in P. I know of a particular problem, though, that is called approximate distance oracles:
Given a weighted undirected graph $G = (V, E)$ with $n = |V|$ nodes and $m = |E|$ edges, a point-to-point query asks for the distance between two nodes $s, t \in V$.
There ...
11
We often seek approximate solutions to simple problems like finding shortest path in a graph, finding number of unique elements in a set. The constraint here is that the input is large and we want to solve the problem approximately using a single pass over the data. There are several "streaming" algorithms designed to achieve approximate solutions in linear/...
11
I meant to leave this as a comment, but I don't have the reputation to do so yet. This question was crossposted over at Mathoverflow, where I mention that the problem is NP-complete.
See here.
To avoid a contradiction with Chandra Chekuri's answer, I do not believe that the LP given in his answer is integral. To see this consider the uniform matroids $...
11
We can get a $(2,2)$ bi-criteria approximation as follows (or more generally $(1+\varepsilon, 1 + 1/\varepsilon)$ bi-criteria approximation).
We may assume that we know the cost of the optimal solution. Denote it by $OPT$. Let
$$w'(u,v) = \frac{w(u,v)}{OPT} + \frac{1}{k}.$$
Consider the optimal solution $(V_1, V_2)$. Then
$$\sum_{(u,v) \in E(V_1, V_2)} w'(...
Only top voted, non community-wiki answers of a minimum length are eligible
