Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
513
questions
-1
votes
1
answer
146
views
approximate maximum clique given vertex cover
I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique of G. One thing I got is that every clique in G ...
- 1
1
vote
2
answers
109
views
Where to find info on (polytime) approximability of various discrete optimization problems?
Where to find info on (polytime) approximability of various discrete optimization problems?
Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of ...
- 21
6
votes
1
answer
147
views
Complexity of approximating a real function using queries
Consider the following computational problem, where $I$ is the real interval $[-1,1]$:
There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of ...
- 2,086
0
votes
1
answer
469
views
What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?
Let $X$ be the universe of elements, $F$ a collection of subsets $S \subseteq X$, each with an associated cost. The goal is to find a subcollection $C \subseteq F$ of minimum total cost which covers $...
6
votes
1
answer
296
views
Good Survey paper for k-means/k-median/k-center/facility-location
I have stated 4 problems in the Question title.
All these problems are closely related and are studied in various variations. For example:
Space: Euclidean/metric/discrete/continuous/non-metric/2-...
- 1,531
10
votes
1
answer
610
views
Is the following graph optimization problem approximable within a constant factor?
Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$.
For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
- 563
1
vote
0
answers
178
views
Separation oracle for hitting all small cut on a graph?
We are given as input an undirected graph $G=(V,E)$, weights $w_e \ge 0$ for all $e\in E$ and an positive integer $k$. We aim to select a set of edges with the minimum weight, such that the cut set of ...
- 461
5
votes
2
answers
244
views
kmeans++ for arbitrary metric spaces and general potential function
I was reading this popular paper "k-means++: The Advantages of Careful Seeding". It appeared in SODA 2007. Since this technique is the most popular clustering technique, I am hoping that my question ...
- 1,531
0
votes
0
answers
40
views
Different version of approximation complexity and algorithm for densest-k-subgraph problem
In the densest-k-subgraph problem, we are given a graph $G =(V,E)$ and $k$, and we are asked to find a set $S \in V$ of vertices to maximize the number of edges in the induced graph of $S$, i.e. $|Ind[...
9
votes
1
answer
908
views
Additive versus multiplicative accuracy
I am trying to understand the difference between $\epsilon$-additive and $\epsilon$-multiplicative algorithms. The way I understand this definition is as follows. An $\epsilon$-additive algorithm is ...
- 193
1
vote
1
answer
157
views
How can I find dependent rounding procedures with the desirable properties?
I'm seeking for materials on dependent rounding. However, what I've found are two papers:
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A., 2006. Dependent rounding and its applications to ...
- 461
1
vote
0
answers
41
views
Efficient algorithm for finding segregators in a directed acyclic graph
Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ...
- 643
4
votes
1
answer
369
views
Approximation Ratio of Local search for $k-$center problem
In the $k-$center problem, you're given $V$ points in Eucledian space, and you're asked to get a subset $C\subset V, |C|=k$ such that $\max _{v\in V}d(v, Closest-Center(C,v))$ is minimized.
Now I am ...
- 1,078
-1
votes
1
answer
92
views
Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed]
Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most ...
- 103
1
vote
1
answer
170
views
Finding the size $k$ subset in a metric space that maximizes the min distance between elements
I have a metric space $(X,d)$ and I'd like to find a subset of size k of far away elements.
We can cast this as the following optimization problem $\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, ...
- 1,439
2
votes
0
answers
105
views
Complexity of a scheduling problem with a fixed left bound of jobs
Consider the following scheduling problem. We have a finite set of jobs $\mathcal{J}= \{j_1, j_2, ..., j_n\}$ to do. Every job $j_i$ has its own value $c_i$ (the amount of money we are paid for ...
-3
votes
1
answer
241
views
is this selection problem np-hard? [closed]
Give $n$ clusters $C=\{C_i\}_{i=1}^n$ where each cluster consists of a set of similar points, i.e., $C_i=\{c_j\}_{j=1}^{|C_i|}$. The similarty between two points $c_i$ and $c_j$ is denoted as $w(c_i,...
- 67
3
votes
1
answer
382
views
Is this greedy algorithm for vertex cover studied before?
For the vertex cover problem (Given a graph $G$, find a minimum set $S$ of vertices such that $G - S$ is edgeless), there are two famous greedy algorithms. The edge greedy (finding an edge and taking ...
- 2,560
-2
votes
1
answer
1k
views
Sequential vs Distributed algo question
If a certain graph problem in the $\textbf{sequential}$ setting is proven to have "no" better constant-factor approximation algorithm than say a 2-approx. algorithm in polynomial time, then does this ...
- 9
-1
votes
1
answer
78
views
the shorstest cycle containing two given points
I am given a edge-weighted (multi)graph $G$ and two of its vertices, $u, v\in V(G)$. I want to find two edge-disjoint paths that connects $u$ and $v$ while minimizing the sum of the lengths of the ...
- 475
4
votes
1
answer
966
views
Is an algorithm with an approximation factor of 4000 useful?
A paper published in SODA this year (2019) proposed a constant approximation algorithm for the lower bounded facility location problem with general lower bounds.
To my surprise, when reading the ...
- 185
5
votes
0
answers
92
views
Relaxed minimum dominating set
(I moved this question from cs exchange to here, because it might be more on the topic here)
Let $G=(V,E)$ be a directed graph with $n$ nodes. For a subset of nodes $S\subseteq V$, let $\mathcal{N}(S,...
- 679
14
votes
1
answer
594
views
Why is the Greedy Conjecture so difficult?
I recently learned about the Greedy conjecture for the Shortest Superstring Problem.
In this problem, we are given a set of strings $s_1,\dots, s_n$ and we want to find the shortest superstring $s$ ...
- 475
5
votes
0
answers
229
views
Martingale exit arguments for gradient Langevin dynamics
I am concerned about the proof of Lemma 6.3 (page 18) of this paper, https://arxiv.org/pdf/1902.08179.pdf which shows that for smooth convex functions the gradient Langevin dynamics has a high ...
- 1,443
6
votes
1
answer
256
views
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
It is known that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard.
There is also a parameterized algorithm for ...
- 9,438
2
votes
0
answers
96
views
Alternative criterion for approximate maximum-weight perfect matching algorithms
I have asked this question in cs.stackeschange, and it was recommended to me that I asked it here.
Is there any literature on approximate maximum-weight perfect matchings where the approximation ...
- 29
2
votes
0
answers
53
views
A "cut" packing problem
Consider the following maximisation problem.
Given a path $P=\{1,2,\dots,n\}$ over $n$ vertices, a set $D\subseteq P\times P$ of "edges" and a set of positive integers capacities $\mathcal{C}=\{c_{i,...
- 475
2
votes
0
answers
129
views
What is the communication complexity of approximating addition?
In my circuit complexity research, I came across the need to find the communication complexity of approximating addition. Specifically, the class of problems I am interested in is parametrized by four ...
- 643
0
votes
1
answer
257
views
finding maximum weight subgraph
My graph is as follows:
I need to find a maximum weight subgraph.
The problem is as follows:
There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in ...
- 67
3
votes
0
answers
95
views
Algorithms for Maximum weight connected subgraph in planar graphs
I wonder what is known about the two following maximisation problems.
Maximum weight connected subgraph :
Input : A graph $G$, with weights $w_v\in \mathbb{R}$ for each vertex $v \in V(G)$
Output :...
- 475
3
votes
0
answers
83
views
Example of a hardness-of-approximation proof which improves the approximation factor?
Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so ...
1
vote
1
answer
388
views
Count satisfying assignments of CNF formulas over all possible negation assignments
Consider the set of all CNF instances that can be generated by adding negations to a single monotone CNF instance. How hard is it to compute the sum of the counts of satisfying assignments for the set?...
- 778
4
votes
0
answers
104
views
$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?
Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following:
$FPT = XPuniform\implies EPTAS = PTAS$.
Fundamentals of Parametrized complexity on page $534$ has
...
- 12.8k
6
votes
1
answer
81
views
NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family
I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following:
There is a value $\...
- 1,424
-1
votes
1
answer
85
views
How is additive error handled in this simple algorithm? 'Product of all elements'
Say we have two unit vectors $\hat{u}, \hat{v} \in \mathbb{R}^n$ where $\hat{u} = (u_1,...,u_n)$ and $\hat{v}$ approximates $\hat{u}$. $~\hat{v} = (u_1+\epsilon, ...,u_n+\epsilon)$ where $\epsilon = \...
-1
votes
2
answers
238
views
Machine Learning Algorithm To Fill Data Holes
I'm having trouble finding a good place to begin with this. I'm just looking for a name or point to start researching a
Let's say I have 1000 records. 10 of these records are only 90% complete. The ...
1
vote
0
answers
47
views
Stable recovery of signals by $\ell_1$ optimization
Suppose the received vector $y$ is generated from a vector $x^*$ as $y = { D}x^* + z$ for some ``dictionary" matrix ${D}$ and noise vector $z$ s.t for some $\epsilon >0$ we have, $\Vert z \Vert_2 \...
- 1,443
4
votes
1
answer
421
views
Intuitive explanation behind Goemans-Williamson randomized rounding
A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more ...
- 10.3k
2
votes
0
answers
144
views
What is the competitive ratio of a $d$-way associative LRU cache?
In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$.
It is well known that for ...
- 9,438
2
votes
1
answer
147
views
Maximum-minimum satisfiability
In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\...
- 2,086
3
votes
2
answers
194
views
Minimum relevant variables in linear system - additive approximation
In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.:
$$ A x = b $$
and the goal is to find a solution $x$ with as few nonzero variables as ...
- 2,086
2
votes
0
answers
172
views
Best polynomial-time approximation factor for NP-optimization problems
Let us say that a function $f(n)$ is the best approximation factor for an NP-optimization problem, if both of the following hold:
There exist a polynomial-time algorithm $A,$ and an integer $n_0$, ...
- 11.3k
6
votes
0
answers
309
views
Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications
Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ...
user17918
1
vote
0
answers
64
views
PTAS for projective clustering : survey
$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below:
Given a $j$-...
- 265
1
vote
0
answers
40
views
Best approach for allocation problem
I am a bit rusty on optimization algorithms and need an advice. This is my problem:
I have n images (with width and ...
1
vote
0
answers
120
views
Why do k min-hashes, instead of one hash where we find the k minimum elements?
Traditionally if one wants to sketch streams for Jaccard similarity hashing, one finds the minimum element in each of $k$ permutation for comparison purposes, and then takes number_of_collisions / $k$ ...
- 729
7
votes
1
answer
336
views
Does Max Planar 3-SAT admit a PTAS?
Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
- 475
5
votes
0
answers
173
views
Classification of randomized approximation algorithms
Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently ...
- 4,439
0
votes
1
answer
86
views
Polynomial approximation algorithm for set cover with assumption
We want to cover $n$ elements with some sets from $S_1, …, S_m$ (classical set cover).
We furthermore suppose that any element belongs to at least $k$ sets and want to find a set cover with cardinal ...
- 129
2
votes
0
answers
150
views
Counting the maximum number of paths of length $n$ that differ in at least $k$ edges
What is known about the complexity of solving (or approximately solving) the following problem?
INPUT: Graph $G=(V,E)$ and constants $L$ and $K$.
OUTPUT: The maximum size of any set $S$ of simple ...
- 1,078