Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Neel Krishnaswami's 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'|$. ...
Yury's user avatar
  • 3,899
13 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 ...
ricardorr's user avatar
  • 561
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-...
Gamow's user avatar
  • 5,772
11 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 ...
Neal Young's user avatar
  • 10.8k
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 ...
PsySp's user avatar
  • 840
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 ...
usul's user avatar
  • 7,615
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 ...
daniello's user avatar
  • 3,266
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 ...
Alex Golovnev's 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.
A.2's user avatar
  • 397
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 ...
Chandra Chekuri's user avatar
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 $\...
Gamow's user avatar
  • 5,772
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" ...
Ted's user avatar
  • 329
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 ...
Martin Hofmann's user avatar
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 ...
holf's user avatar
  • 2,174
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 ...
Michael Lampis's user avatar
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:...
Emil Jeřábek's user avatar
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 ...
Hermann Gruber's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
5 votes

Can we approximate the number of words accepted by an NFA?

And now there is a faster FPRAS: https://arxiv.org/abs/2312.13320
Umang's user avatar
  • 111
5 votes

W[1]-hard problems with FPT time approximation algorithms

The k-cut problem is to remove a minimum number of edges to create at least k components. W[1] hard when parameterized by k but admits a 2-approximation for any k.
Chandra Chekuri's user avatar
5 votes

W[1]-hard problems with FPT time approximation algorithms

(This question was asked two years ago, but I'll post the answer for other people who may see this question.) In the Capacitated $k$-median problem we are given a set $F$ of facilities, each facility ...
Amir Nikabadi's user avatar
5 votes

Max cut problem between two connected subgraphs

Here is a straightforward reduction from the max-cut problem: Take any graph and add two new vertices $u,v$ and connect them to every other vertex with weight 0 and connect them to each other by a ...
Saeed's user avatar
  • 3,440
5 votes
Accepted

Is this greedy algorithm for vertex cover studied before?

Unfortunately, the algorithm can be arbitrarily bad. In the following example, each vertex $u_i$ has $d$ disjoint neighbors, of which only four are drawn. The optimal solution is $\{u_1, \ldots, u_p, ...
Yixin Cao's user avatar
  • 2,559
5 votes
Accepted

Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

See Feige and Jozeph's paper on separation between estimation and approximation.
Chandra Chekuri's user avatar
5 votes
Accepted

Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$

Theorem 1. For any $\epsilon>0$, there is a $(1+\epsilon)$-approximation algorithm that makes $O(\epsilon^{-1}\log n)$ queries. Note that if $\epsilon$ is arbitrarily small but constant, the ...
Neal Young's user avatar
  • 10.8k
4 votes
Accepted

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

(Comment $\rightarrow$ Answer) Consider the following algorithms for a hypergraph $(U,\mathcal S)$, with $n=|U|$: For a set $X\subseteq \mathcal S$ of sets and a set $A \in X$, define $d_X(A)$ as ...
Yonatan N's user avatar
  • 1,642
4 votes
Accepted

Solution/Hardness of the following (integer) budgeted problem?

Solving this exactly this ends up being $\mathsf{NP}$-hard. The reduction I have doesn't pay much attention to the representation of the $f_i$'s. That said, the values of $f_i$ I end up giving can be ...
Andrew Morgan's user avatar
4 votes

Ordering of a DAG minimizing some definition of cost

This problem is NP-complete, as the following reduces to it: https://cstheory.stackexchange.com/a/1936/419 The sketch of the reduction is as follows. From a set of tasks $T$ with $n$ tasks and some ...
domotorp's user avatar
  • 14k
4 votes

Approaches for Theoretical Analysis of Estimates of Probability Distributions

Disclaimer: I am biased, in that I will suggest a survey which I have written. What you seem to be looking for can be captured under the field of distribution testing, a subfield of Property Testing ...
Clement C.'s user avatar
  • 4,471

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