27
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 ...
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
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 ...
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
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
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 $\...
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
11
The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$.
Observation. An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ is ...
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
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 ...
10
There are many open algorithmic problems. All problems below (other than the last bullet) are NP-hard, so we are interested in the best approximation ratio we can achieve in polynomial time. The following are just a sample:
Given a non-negative submodular function on a universe $U$, find a set $A$ of size at most $k$ maximizing $f(A)$. The best known ...
10
One relevant TSP version is "Group TSP". In this problem, the "cities" are divided into groups and the goal is to find a tour that visits each group at least once.
This has also been studied on the plane, which is closer to what you describe. Here each group is a closed region of the plane and it suffices to visit one point in the region to cover it. See e....
10
Cormen, Leiserson, Rivest and Stein say that this algorithm that achieves ratio of 2 is tight. They did not exclude the possibility of another algorithm achieving better.
Vertex Cover is NP-hard to approximate with a factor better than 1.36:
http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf
Also check the following paper which give ...
9
Isn't this a special case of matroid intersection,
which is solvable in polynomial time?
Fix your graph $G$ and any integer $d \in \{0,1,\ldots,\max_i a_i\}$.
You want to maximize $d$; you can try all possibilities.
For a given $d$, you want to answer the following question:
Is there is a spanning tree $T$ such that $\max_i a_i - \mbox{deg}_T(u_i) \le d$?...
9
As stated, your approach is problematic, because if 2 bitmaps have evenly spaced differences then in any rotation, there will be differences on some high order bits.
You can generalized your approach by permuting the bit position in a more complex fashion. Indeed, if you select a random permutation of bits, then all differences between 2 bitmaps with ...
9
Alon, Matias, and Szegedy proved that finding the frequency of the most frequent of $n$ items requires $\Omega(n)$ space in the worst case in the streaming model, even if you allow a constant number of passes over the input. Since finding the most frequent item gives you a two-pass algorithm for computing its frequency (find in the first pass, track its ...
9
The Lovász $\vartheta$ function is an efficiently computable function with the property
$$
\alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G),
$$
where $\alpha$ is independence number and $\bar{\chi}$ is clique cover number. If the bound $\frac{\bar{\chi}(G)}{\alpha(G)} \leq n^{1-\varepsilon}$ were true for some constant $\varepsilon > 0$, then we would have ...
9
If $p$ is constant, then the size of the maximum clique in the $G(n,p)$ model is almost everywhere a constant multiple of $\log n$, with the constant proportional to $\log (1/p)$. (See Bollobás, p.283 and Corollary 11.2.) Changing $p$ should therefore not affect the hardness of planting a clique with $\omega(\log n)$ vertices as long as the clique is too ...
9
This is a combination of comments from me and Chandra Chekuri above, elaborated a bit.
As background, if you have a partial matching then its symmetric difference with the optimal matching can be decomposed into disjoint alternating paths (and possibly also some alternating cycles but those can be ignored). Hopcroft–Karp maintains a partial matching as it ...
9
In the Directed Odd Cycle Transversal problem the input is a graph $G$ and the task is to find a smallest set $S$ of vertices such that $G-S$ has no (directed) cycles of odd length. In the parameterized version we are also given an integer $k$ and asked whether a solution of size at most $k$ exists.
In this paper we prove that (R1) the problem is W$[1]$-...
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
To complement the other answer: Costello, Shapira and Tetali showed that the expected approximation ration achieved by Johnson's algorithm on a random permutation of the variables is strictly better than $\frac{2}{3}$. Poloczek and Schnitger showed that another randomized version of the algorithm has expected approximation ratio $\frac{3}{4}$, and that the ...
8
I think for getting 1.99-approximation algorithm this paper by Manurangsi and Trevisan, has the current fastest algorithm.
8
Let me first try to summarize what is known about the Greedy Conjecture.
Blum, Jiang, Li, Tromp, Yannakakis prove that the Greedy Algorithm gives a 4-approximation, and Kaplan and Shafrir show that it gives a 3.5-approximation for the Shortest Common Superstring problem.
A version of the greedy algorithm is known to give a 3-approximation (Blum, Jiang, Li, ...
Only top voted, non community-wiki answers of a minimum length are eligible
