Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
513
questions
2
votes
1
answer
163
views
About a pre-processing step for primal–dual weighted set cover problem
I was reading the paper titled "Primal-dual RNC approximation algorithms.." by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.
They present a dual fitting based algorithm ...
- 23
3
votes
2
answers
567
views
Finding a set which dominates the Minimum Dominating Set
Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$.
The dominating set problem is NP-hard, but I am considering ...
- 607
2
votes
0
answers
38
views
Approximate answer to Max-SMT (bitvector) query
I have a problem that could be completely solved as Max-SMT instances in the theory of quantifier-free bit-vectors, but it apparently is too complex to be tractable with current Max-SMT technology. ...
- 433
6
votes
2
answers
544
views
Max cut problem between two connected subgraphs
Let $G$ be a connected graph.
Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known ...
- 1,439
3
votes
2
answers
372
views
What is the best approximation and exact algorithm for vertex cover on cubic graphs?
"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
- 41
1
vote
0
answers
85
views
k-center 2.0: A stronger k-center condition
Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$.
Note that ...
- 607
3
votes
1
answer
58
views
Complexity of distributively verifying that the diameter is small
Consider a graph $G=(V,E)$ and an integer parameter $k$.
I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
- 9,438
7
votes
1
answer
140
views
Smoothed analysis to compare algorithms
Has there been any research using smoothed analysis to compare approximation algorithms that have the same approximation ratio?
Any research that compares algorithms using smoothed analysis would be ...
0
votes
1
answer
104
views
How can algorithms with nested combinatorial searches be quasi-linear?
I've come across algorithms similar to the one below, where a demanding step is performed, which should have at least polynomial complexity, yet the whole algorithm is deemed quasi-linear without ...
- 111
9
votes
5
answers
1k
views
W[1]-hard problems with FPT time approximation algorithms
I'm looking for problems that are hard to solve in FPT time but has an approximation algorithm. That is, problems that are:
R1. W[1]-hard.
R2. Admit a (preferably constant) approximation algorithm ...
- 9,438
2
votes
0
answers
90
views
Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)?
In online-setting, we usually allow exponential time to think and come up with a strategy. On the other hand, in offline-setting, we might care about solving a particular problem optimally, or as good ...
- 21
1
vote
1
answer
80
views
Does the following 2-rounds distributed algorithm approximates a maximal matching well?
Let $G$ be an undirected graph.
I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible.
Consider the following protocol for vertex $v$.
Use a fair coin to ...
- 9,438
2
votes
0
answers
273
views
Can we find a generic tight example for the greedy algorithm of the unweighted generalized assignment problem?
In the unweighted generalized assignment problem (UGAP) we have $n$ items and $k$ knapsacks. For each item $i$ and knapsack $j$, there is a weight $w_{ij}$. Also, every knapsack has a capacity $W$. ...
- 115
1
vote
1
answer
279
views
Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?
I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph.
Input: Given a graph G with non-negative vertex weights and valid ...
- 193
1
vote
1
answer
246
views
Minimizing SubModular Function: Cardinality
Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| <= k and such that f(S) is minimized.
When the size constraint is |S| >=k, the ...
- 19
0
votes
1
answer
116
views
About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective
Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?
- 1,443
1
vote
0
answers
61
views
What is the fastest gradient based algorithm to get to criticality of a "nice" non-convex function?
I am allowing for the following properties for a once differentiable non-convex $f : \mathbb{R}^d \rightarrow \mathbb{R}$,
(a) Let there be a $\sigma >0$ s.t the norm of the gradient of the ...
- 1,443
4
votes
0
answers
571
views
Hardness of Approximation for minimum path cover in an undirected graph?
Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path ...
- 53
1
vote
0
answers
33
views
Getting to local/global minima with (stochastic) gradient descent on non-convex objectives
Is there any class of non-convex objective functions for which (stochastic) gradient descent can provably get to a local or a global minima? (..maybe in the approximate sense like a point such that ...
- 1,443
3
votes
0
answers
46
views
Approximating a monotone submodular function using a concrete coverage function
Is it possible to approximate a monotone submodular function using a concrete coverage function, i.e.
Given a ground set $U$ and a monotone submodular function, $f:2^U\to \mathbb{R}$, the goal is to ...
- 143
1
vote
1
answer
284
views
Monotone supermodular function minimization under partition matroid constraints
Is there a known approximation algorithm for the problem of minimizing
a monotone (non increasing) supermodular function under partition matroid constraints ?
- 143
4
votes
0
answers
123
views
Learning hidden variable distribution
Consider a set of $k$ continuous variables. Each variable $x_k$ is associated with a hidden distribution from which its value is sampled independently of other variables. I am given a set of ...
- 1,177
3
votes
0
answers
131
views
Stacks serving interval storage requests
An interval storage request is represented by a tuple $(s,t,v)$ satisfying $s<t$, meaning that the value $v$ needs to be stored from time $s$ to time $t$. A stack serves the request $(s,t,v)$ in ...
- 437
2
votes
0
answers
113
views
Unbalanced connected partition
Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are ...
- 121
1
vote
1
answer
756
views
Common terminology used for lower/upper bounds
Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound?...
- 111
6
votes
0
answers
191
views
An optimal subspace projection problem
Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that
$$\...
- 271
0
votes
2
answers
253
views
Geometric max cover
Consider $n$ points and a distance function $d$ that satisfies the triangle inequality. We are also given a number $r$.
Each point $p$ defines a set $B_p$ (or a ball) that covers all other points ...
10
votes
1
answer
520
views
Find an approximate argmax using only approximate max queries
Consider the following problem.
There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query ...
- 2,803
1
vote
0
answers
67
views
\alpha-path on Euclidean graphs
Consider the following problem:
Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights ...
- 11
1
vote
0
answers
134
views
Hausdorff Distance and Convex Hull
Given two sets of points A and B, both in $R^d$, is there a relation between the convex hulls of A and B, i.e. conv(A) and conv(B), w.r.t. the Hausdorff distance between A and B? In other words, does ...
- 209
6
votes
0
answers
181
views
Lower bound for Yao's algorithm on general addition chains?
An addition chain of size $n$ for given integers $n_1,n_2\dots ,n_p$ is a sequence of integers $k_1,k_2\dots ,k_n$ such that
$k_1=1$,
for all $i$ $(2\le i\le m)$ we have $k_i=k_j+k_m$ for some $1\le ...
- 500
3
votes
0
answers
118
views
On approximating problems in $\#P$
We know that for every counting problem $\#A$ in $\#P$, there is a probabilistic algorithm
$\mathcal C$ that on input $x$, computes with high probability a value $v$ such that $$(1 − ε)\#A(x) ≤ v ≤ (1 ...
- 12.8k
2
votes
0
answers
85
views
On the impossibility of representing/approximating subadditive function using additive functions
I am trying to understand whether a monotone and subadditive function $f(S), S \subseteq 2^{[n]}$ and $ f : 2^{[n]} \rightarrow R_{\geq0}$ can be represented using an additive function $\hat{f}(S) = \...
- 1,177
1
vote
1
answer
137
views
Practical/heuristic algorithm for multi set-cover
Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ ...
- 771
1
vote
1
answer
844
views
Clique cover problem
Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $...
- 119
0
votes
1
answer
85
views
Approximating max degree $3$ perfect matching count?
We do not have a deterministic constant factor approximation scheme for general $n\times n$ $0/1$ permanent.
What is the best factor in deterministic approximation schemes if we only care counting ...
- 12.8k
3
votes
1
answer
147
views
Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?
We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$...
- 31
1
vote
1
answer
117
views
hardness of constant approximation of largest matching set
We say that $H$ is a matching graph if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more.
Given a graph $G=(V,E)$ a subset $U\subseteq V$...
- 153
2
votes
0
answers
218
views
Approximating the Radius of a (Dense) Graph
For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius.
A $(1+\epsilon)$-approximating of APSP for a ...
- 230
14
votes
2
answers
755
views
Proof assistant usage in complexity theory research?
Considering the topics covered at a conference like STOC, are any algorithm or complexity researchers actively using COQ or Isabelle? If so, how are they using it in their research? I assume most ...
- 385
1
vote
0
answers
72
views
Sparse-cut approximation for well connected graphs
Theorem: For any graph $G=(V,E)$, there is a polynomial time algorithm that finds a cut $S \subseteq V$ with conductance at most $\sqrt{2\big(1 − \lambda(G)\big)}$.
If I understand UGC correctly, ...
- 771
2
votes
0
answers
63
views
Studying the hardness of polynomial-time approximability using the concept of stability of approximation
In the Conclusion section, the author of this paper "Stability of Approximation Algorithms for Hard Optimization Problems" by Juraj Hromkovič, 1999 claims that
Using the notion of stability one can ...
- 2,329
2
votes
0
answers
114
views
Alternative Set Cover Algorithm With Doubling
I remember that I saw once an alternative to the greedy set cover algorithm that works as follows:
Assign weight 1 to every element in the universe. Repeat steps 2 and 3 until the universe is covered:...
- 121
7
votes
0
answers
119
views
Deterministic approximation algorithms for treewidth
As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee is randomized, and no deterministic approximation algorithm with this factor ...
- 3,256
1
vote
0
answers
41
views
Sparse coding and matching pursuit algorithms
Is it true that all known sparse coding algorithms which work efficiently in practice don't have convergence proofs and always use an intermediate step of a matching/subspace pursuit algorithm on the ...
- 1,443
1
vote
0
answers
86
views
Is it sufficient to only check on the vertices? Greedy algorithm
Suppose that I have a downwards closed Polyhedron and a vector $\omega$ and a greedy algorithm that goes as follows:
Given an initial $x_0$, order the indices of $\omega$. Then for each $i$, solve $\...
- 19
1
vote
0
answers
64
views
What is known about data structures for encoding a set while considering approximate Rank queries?
Consider a universe $\mathcal U\triangleq \{1,2,\ldots n\}$, and assume that we are given a set $S\subseteq \mathcal U$.
There are many data structures that allow storing $S$ while answering Rank ...
- 9,438
3
votes
1
answer
318
views
Looking for approximation class between NPO and Exp-APX
I'm trying to identify the approximation hardness of some maximization problem A. In problem A, finding a solution whose quality is 0 (i.e. such that the value returned by the objetive function is 0) ...
- 373
5
votes
0
answers
226
views
Why is HyperLogLog (near-)optimal?
The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads:
Clearly, maintaining $\epsilon$-approximate counts till ...
- 329
1
vote
2
answers
3k
views
Is the current best approximation ratio for Vertex Cover problem also a lower bound?
In textbook "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein. in pp.1110-1111, they argue that the vertex-cover problem is a 2-approximation algorithm and it is lower bound so we ...
- 193