12

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 ...


7

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 real interval such as $[0, c]$. For example, the paper you mention is about computing approximation solutions to two-player zero-sum matrix games in which the ...


6

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 understanding correctly, thanks. Consider a cluster $X$ consisting of a rooted star: a root $r$ and $n-1$ nodes $v_1,v_2,\ldots, v_{n-1}$ such that $d(r, v_i) = 1$...


4

The best approximation ratio that can be achieved in polynomial time should be $\Theta(\log n)$ where $n$ is the number of vertices. This can be seen by standard reductions from the Set Cover problem which is NP-hard to approximate within a factor of $(1-\alpha)\cdot N$ where $N$ is the input size [1]. First, we use the standard reduction from Set Cover to ...


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 ...


4

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/


4

Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the minimal number of evaluation queries needed to uniquely identify $f$? As already noted in the OP, the question only makes sense if one fixes a function class $...


3

Local search (with a single swap) doesn't give you a good approximation factor in the worst case for $k$-center, as illustrated by the following example. Take a simplex in $\mathbb{R}^{k-1}$, and put $k$ points at each of the $k$ vertices, for a total of $k^2$ points. Note that between each pair of vertices of the simplex the distance is 1. The optimal ...


2

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time you cover an element, update the cost of all sets that cover it. Then there are n total updates, so the total time for the algorithm using a priority queue in ...


2

Recently, I came across the following survey: Recent Developments in Approximation Algorithms for Facility Location and Clustering Problems The authors only discuss the major results and mention some interesting open problems at the end.


2

The statement of the problem is incorrect. But $T$-joins are indeed very much related to the perfect matching problem. What the theorem that 9.3a is supposed to be conveying is: Assume $G$ is connected. Suppose that $T = V$. The minimum $T$-join can be found as follows: construct a complete graph $G'$ such that the weight on an edge (a,b) in $G'$ is the ...


1

Since it is asymptotic approximation and epsilon is a constant, for OPT big enough being 1 off is always good. Let's put it another way. Either your optimal is smaller than 1/epsilon and you can find it within polynomial time. Or it is not and thus 1+1/OPT is better than 1+epsilon.


1

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


1

Dependent randomized rounding is a broad tool that is used in many approximation algorithms. Lot depends on the problem structure, objective and constraints and there is no single unified answer/framework. Some papers like the ones you mention identify generic settings where one has some nice probabilistic tools and provide some applications. I list a paper ...


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 ...


1

To simplify life, let $\mathcal V = [n] := \{1,2,\ldots,n\}$. For $A \subseteq [n]$, define $h(A):=\sum_{i \in A}c_i$. Note that $h$ defines a modular (i.e additive) set function. Now, suppose there exists $\gamma \in [0, 1]$ such that $f$ is weakly $\gamma$-submodular, i.e such that $$ \sum_{i \in B\setminus A}f(A \cup \{i\}) - f(A) \ge \gamma (f(A \cup B)...


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