# Tag Info

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