56
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$-...
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 ...
26
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
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
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 ...
14
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 ...
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$.
...
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
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'(...
11
Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach.
This has been observed, for instance, in Theorem 17 in
Pierluigi Crescenzi and LucaTrevisan:
"Max NP-completeness made easy"
Theoretical Computer Science 28, (1999), Pages 65-79
10
Fast approximation algorithms for maximum matching are known. Atleast one that that comes to my mind immediately is http://arxiv.org/pdf/1112.0790v1.pdf.
10
EDIT (UPDATE): The lower bound in my answer below was proven (by a different proof) in "On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees", by Das et al; Algorithmica 19:447-460 (1997).
is it possible to achieve even an approximation ratio like $O(n^{1-\epsilon})$ for some $\epsilon>0$ in $o(n\log n)$ time ...
10
The motivation you state for dealing with undecidability applies to decidable but hard problems as well. If you have a problem that is NP-hard or PSPACE-hard, we will typically have to use some form of approximation (in the broad sense of the term) to find a solution.
It is useful to distinguish between different notions of approximation.
Numeric ...
10
One paper that gives an answer to this question is Chalermsook, Laekhanukit, & Nanongkai (2013).
There are also related works in the context of Fixed Parameter Tractability such as
Hajiaghayi, Khandekar, & Kortsarz (2013) and Chitnis, Hajiaghayi, Kortsarz (2013).
These hardness results are proven under various assumptions such as ETH or existence of ...
10
The answer to the title question is: it's difficult to simulate a Markov chain with negative transition probabilies.
Valiant's reduction uses the Chinese remainder theorem, which requires an exact number, not just an approximation. The JSV algorithm cannot tell you what the permanent of a matrix is modulo 3, for example.
The type of reductions you'd need ...
10
We're interested in additive approximations to #3SAT. i.e. given a 3CNF $\phi$ on $n$ variables count the number of satisfying assignments (call this $a$) up to additive error $k$.
Here are some basic results for this:
Case 1: $k=2^{n-1}-\mathrm{poly}(n)$
Here there is a deterministic poly-time algorithm: Let $m=2^n-2k = \mathrm{poly}(n)$. Now evaluate $\...
10
If you insist on precise partition, then you need to compute all the balanced partitions of a set of points in the plane by a line (the optimal partition is a Voronoi partition, so the two point sets are separated by a line). Such partitions are known as $k$-sets. The fastest algorithm currently known for this work in $O(n^{4/3} \log n)$ for computing these ...
Only top voted, non community-wiki answers of a minimum length are eligible
