22
votes
Accepted
What is known about this TSP variant?
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, ...
- 4,503
15
votes
Accepted
Proof assistant usage in complexity theory research?
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 ...
- 31.7k
14
votes
Accepted
Is the following graph optimization problem approximable within a constant factor?
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'|$. ...
- 3,844
11
votes
Accepted
Can we approximate the number of words accepted by an NFA?
There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $n$ accepted by a NFA in the general case (without restricting to the acyclic ...
- 521
11
votes
Accepted
Does Max Planar 3-SAT admit a PTAS?
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-...
- 5,722
10
votes
What is known about this TSP variant?
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 ...
- 3,094
10
votes
Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?
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 ...
- 14.1k
10
votes
Accepted
Is the current best approximation ratio for Vertex Cover problem also a lower bound?
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 ...
- 780
10
votes
Accepted
Find research partner (profession and beginner)
I don't know of such a page. Most researchers have specific problems that they are interested in working on, and would only want to collaborate on those. If you pick a particular area and focus on ...
- 7,090
9
votes
Accepted
Modifying Hopcroft-Karp algorithm to get approximate bipartite matching
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 ...
- 50.3k
9
votes
Accepted
W[1]-hard problems with FPT time approximation algorithms
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 ...
- 3,236
9
votes
Why is the Greedy Conjecture so difficult?
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 ...
- 2,153
8
votes
Accepted
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
I think for getting 1.99-approximation algorithm this paper by Manurangsi and Trevisan, has the current fastest algorithm.
- 387
7
votes
The Goemans-Williamson algorithm in the $SOS$ framework
Looking at the Goemans–Williamson algorithm in the SOS framework yields no technical advantages: it is exactly the same algorithm and the same ideas are used in the analysis.
The only advantages in ...
- 3,721
7
votes
Accepted
Additive versus multiplicative accuracy
Why is it sometimes easier to achieve $\epsilon$-additive accuracy than $\epsilon$-multiplicative?
Consider a problem where the objective value OPT is guaranteed to lie in a constant non-negative ...
- 8,281
6
votes
Accepted
Inapproximability of $(\alpha, \beta)$ bi-criteria approximation
This problem generalizes dominating set: given an unweighted graph, there exists a set of k centers such that all other vertices are at distance 1 from them if and only if there exists a dominating ...
- 3,094
6
votes
Is there a sensible notion of an approximation algorithm for an undecidable problem?
This is answering the title of the question more than its content, but you can also consider "approximations" of the halting problem as algorithms which will give you a correct answer on "almost all" ...
- 329
6
votes
Accepted
What is the intuition behind "hardness of approximation"?
One important reason why problems that look equally hard to compute exactly might be very different to approximate relates to the fragility of NP-completeness reductions.
The simplest example I can ...
- 31.8k
6
votes
Accepted
Set cover in which some pairs of sets are forbidden
This problem is way harder than set cover. Here is why...
Intuitively, you can encode independent set as a problem of this type. Indeed, you are given an instance of independent set - a graph $G$ ...
- 9,566
6
votes
Coreset and VC dimension
Samples provides you only with statistical guarantees. For a fixed $\epsilon$ whatever you compute would hold for everything "except" $(1-\epsilon)$ fraction (I am being very informal here). Thus, ...
- 9,566
6
votes
What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
The relaxation of Calinescu, Karloff and Rabani for the undirected Multiway Cut problem is one my favorites. Had a big influence on subsequent work.
http://www.sciencedirect.com/science/article/pii/...
6
votes
Accepted
The complexity of decomposing a bi-stochastic matrix
Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using $O(\max\{n^{d+2},n^4\})$ operations over the reals for ...
- 8,841
6
votes
Does k-PATH admit a constant approximation?
Karger, Motwani and Ramkumar (1997) discuss this question.
They show that if any polynomial-time algorithm can approximate the longest path to a ratio of $2^{O(\log^{1−\epsilon} n)}$, for any $\...
- 5,722
6
votes
Accepted
How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?
The "dual bin packing problem" is more commonly referred to as the Multiple Knapsack problem. One can show that $ALG \ge (1-1/e) OPT_b$ assuming an optimal algorithm for the Knapsack problem is used ...
- 6,659
6
votes
Proof assistant usage in complexity theory research?
One very prominent example is of course Gonthiers Coq formalization of the 4 color theorem in Coq which uses a lot of combinatorics.
My colleague Uli Schöpp used the ssreflect library developed by ...
- 603
6
votes
W[1]-hard problems with FPT time approximation algorithms
In [1], the authors prove that MaxSAT parametrized by the clique-width (resp. neighbor diversity) of the incidence graph of the CNF formula has an FPT-AS (Fixed Parameter Tractable Approximation ...
- 1,854
6
votes
W[1]-hard problems with FPT time approximation algorithms
In Defective Coloring we are given a graph $G$ and an integer $\Delta^*$ and are asked to partition the vertices of $G$ into the minimum possible number of color classes so that each class induces a ...
- 3,094
6
votes
Accepted
Count satisfying assignments of CNF formulas over all possible negation assignments
The quantity $\sum_k|\phi_k|$ can be computed in polynomial time, in fact, in uniform $\mathrm{TC}^0$. By double counting, we have
$$\sum_k|\phi_k|=|\{(a,k):a\models\phi_k\}|=\sum_{a\in\{0,1\}^n}|\{k:...
- 14.9k
6
votes
Accepted
Is an algorithm with an approximation factor of 4000 useful?
A very good question! While I think a feasible solution which is 4000 times worse than the optimum is often not very practical, if you have several approximation algorithms to choose from, I would ...
- 5,444
6
votes
Accepted
kmeans++ for arbitrary metric spaces and general potential function
Here's an example that suggests that the stronger claim in the earlier version (Lemma 5.3) is false. I've only given a cursory look at the papers, so please check this carefully to make sure I am ...
- 8,281
Only top scored, non community-wiki answers of a minimum length are eligible