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, ...
user avatar
  • 4,493
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 ...
user avatar
14 votes
Accepted

Why is complementary slackness important?

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 ...
user avatar
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'|$. ...
user avatar
  • 3,844
12 votes
Accepted

Approximating #P-hard problems

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 ...
user avatar
  • 2,743
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 ...
user avatar
  • 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-...
user avatar
  • 5,712
10 votes

Bisecting a set of points into two optimal subsets

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 ...
user avatar
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 ...
user avatar
  • 14.1k
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 6,997
9 votes
Accepted

Planted Clique in G(n,p), varying p

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....
user avatar
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 ...
user avatar
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 ...
user avatar
  • 3,161
8 votes

Greedy MAX SAT approximation ratio

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 ...
user avatar
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.
user avatar
  • 387
8 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 ...
user avatar
7 votes
Accepted

Tight examples for approximating the feedback vertex set problem

I think you can make the classical local ratio algorithm by Bafna et al. give a $2-o(1)$ approximation on the following family of graphs: Take $G_n$ to be a $K_{n,n}$ (the complete bipertite graph ...
user avatar
  • 9,348
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 ...
user avatar
  • 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 ...
user avatar
  • 8,133
6 votes

The number of integral points in a polytope

Check out https://www.math.ucdavis.edu/~latte/ and the corresponding paper Effective lattice point counting in rational convex polytopes. Jesús A. De Loera, Raymond Hemmecke, Jeremiah Tauzer, ...
user avatar
  • 1,713
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" ...
user avatar
  • 329
6 votes

What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?

If one wants to approximate the potential function, then yes, there even exists a fully polynomial-time approximation scheme (FPTAS). See James B. Orlin, Abraham P. Punnen, Andreas S. Schulz: ...
user avatar
  • 1,713
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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, ...
user avatar
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 ...
user avatar

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