11

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 NFA case). The result was published this year on STOC, by Arenas, Croquevielle, Jayaram and Riveros. Here is the talk https://youtu.be/tyK-uujHMLU and the paper ...


10

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 developing your expertise and interests in that area, you could potentially reach out to individual researchers working on the same problems as you. For example, I ...


5

See Feige and Jozeph's paper on separation between estimation and approximation.


4

Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$. We can at least prove that if $x$ is chosen uniformly from $[0,1]$, then the average variance must be at least $\pi^2/64 - 1/12$. There is a dithering algorithm that achieves this average-case ...


3

These are not directly comparable: Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual approximation ratio. The paper mentioned in the question and related work: find a cut in any graph G [of some graph family] that contains at least X fraction of ...


3

To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard). In "Parameterized Algorithms to Preserve Connectivity" they show that a Cactus Augmentation Problem can be transformed into an equivalent Node-weighted Steiner Tree problem where each Steiner node is ...


3

We improve Chandra's bound, as he conjectured was possible, giving an approximation algorithm that opens $f(k,\epsilon)=O(k\log (1/\epsilon))$ facilities to obtain assignment cost at most $1+\epsilon$ times the optimal with $k$ facilities. Theorem 1. There is a polynomial-time algorithm that, given any metric $k$-medians instance, returns a solution that ...


2

The answer to Question (1) is no. The answer to Question (2) is yes. Here are the details. I'll work with the following equivalent problem formulations. For the input, we are given $n$ pairs of values $(v_1, w_1), (v_2, w_2), \ldots, (v_n, w_n)$ in $\mathbb R^2_+$. Problem A. Find $\max\big\{ \sum_{i\not\in S} v_i : S\subseteq [n],\, \sum_{i\not\in S} w_i ...


2

Theorem 1. The problem admits a 2-approximation algorithm that runs in $O((m+n)\log n)$ time, given a graph $G=(V,E)$ with $m$ edges and $n$ vertices. [Caveat: The current post doesn't specify the objective-function value if one or both of the clusters contains no edges. I assume that the objective-function value only sums the maximum-weight edges within ...


2

The problem even seems to be solvable in polynomial time. Let us call $C_1$ the black cluster and $C_1$ the white cluster. We test for every two edges $e_1,e_2\in E$ whether there exists a bipartition so that $e_1$ is the heaviest edge in $C_1$ and $e_2$ is the heaviest edge in $C_2$. In the end, we ouput the bipartition that minimizes the sum of the two ...


2

Using Chandra's hint, I think I got the idea. We bounded the probability: $$Pr(G_i \leq b_i) \leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}}$$ Now consider an item of size $s_i$ that was left. It was left out because we didn't sample a configuration that contains it. This happens with probability $$(1-\sum_{j:{\bf T_j} \text{ contains item }i}\frac{x_j}{z^\...


1

Maybe this will give ideas for a faster algorithm: Theorem 1. There's an $O(n^2 \log n)$-time 2-approximation algorithm. Proof. Here's the algorithm: Using binary search over the $O(n^2)$-pairwise distances $\{d(u,w) : u, w\in V\}$, find the minimum radius $r$ such that the graph $G_r=(V, E_r)$ is bipartite, where $E_r = E \cup\{(u,w) : d(u, w) > r\}$. ...


1

Take an arbitrary instance $S_1,\ldots,S_n$ of SET COVER. Between $S_1$ and $S_2$, insert a chain of new subsets $$ S_1-x,~ S_1-\{x,y\},~ \ldots,~ \{z\},~ \emptyset,~ \{c\},~ \ldots,~ S_2-\{a,b\},~ S_2-\{a\}.$$ Do the same for all other pairs of consecutive sets. The resulting instance satisfies your condition, and it is equivalent (with respect to ...


1

Historically Lin and Vitter showed that one can obtain a $(2+\epsilon, k(1+1/\epsilon))$ bi-criteria approximation via a simple filtering trick with respect to the LP. This was before a constant factor approximation was shown via the LP. After that there seemed to be less interest in a bi-criteria PTAS even though it was explored extensively in geometric ...


1

After a bit more searching, it appears that what I'm looking for is unlikely to exist. In [1], it is proven that approximating the minimum maximal independence number (which is equivalent to the minimum size of an independent dominating set) within a factor of $O(n^{1-\epsilon})$ is $\mathrm{NP}$-hard for any $\epsilon > 0$. This remains true even when ...


1

Though unrelated, this lecture note contains a potential function based neat proof of the $O(\log k)$-approximation.


1

For the non-metric $k$-median problem, we can show a stronger inapproximability result than $O(\log n)$. The following is a stronger claim: Main Claim: The non-metric $k$-median problem can not be approximated to any factor better than $n^{c}$, for any constant $c>0$. Proof: The proof follows from the reduction from the hardness of the max $k$ coverage ...


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