Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

Filter by
Sorted by
Tagged with
1
vote
1answer
26 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 ...
0
votes
0answers
29 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[...
2
votes
1answer
80 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 ...
1
vote
1answer
63 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 ...
0
votes
0answers
30 views

Polynomial time multiplicative approximation algorithms for logistic regression?

Typically algorithms for logistic regression have an iterative aspect since the problem does not admit a closed form solution. By extension, most iterative algorithms (gradient descent etc.) for ...
1
vote
0answers
33 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$ ...
2
votes
1answer
57 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
votes
1answer
58 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 ...
0
votes
1answer
80 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, ...
2
votes
0answers
94 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
1answer
102 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,...
3
votes
1answer
131 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
votes
1answer
511 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 ...
-1
votes
1answer
68 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 ...
4
votes
1answer
951 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 ...
5
votes
0answers
60 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,...
0
votes
0answers
58 views

What is the run-time of LP?

Are there any further generalizations known to the result about run-time of a LP than what is stated in Theorem 1 of these lecture notes, https://nisheethvishnoi.files.wordpress.com/2018/05/lecture71....
0
votes
0answers
40 views

Approximate nearest neighbor search for $(\ell_p)^p$ metric, $0 < p < 1$

It is well known that approximate bichromatic nearest-neighbor search can be solved in sub-quadratic time for the $\ell_1$ and $\ell_2$ norms, as well as some other metrics. Are there any such results ...
14
votes
1answer
353 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$ ...
5
votes
0answers
216 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 ...
6
votes
1answer
230 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 ...
1
vote
0answers
79 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 ...
2
votes
0answers
51 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,...
2
votes
0answers
91 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 ...
0
votes
1answer
103 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 ...
3
votes
0answers
55 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 :...
3
votes
0answers
71 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 ...
0
votes
0answers
24 views

Algorithmic gap for greedy algorithm for (metric) uncapacitated facility location

In Jain et. al (2003), at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega(\frac{\...
0
votes
0answers
28 views

Two question regarding coreset construictions

I have two questions regarding coreset construction of clustering problem In A Unified Framework for Approximating and Clustering Data, a very general framework is given to construct coresets for ...
0
votes
0answers
60 views

Linear time algorithm for projective clustering

There is a lot of work in clustering of high dimensional data. In case of k-means, it is shown here that one can get an $(1+\epsilon)$-approximation in linear time, yielding a PTAS, by random sampling....
1
vote
1answer
152 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?...
3
votes
0answers
71 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 ...
6
votes
1answer
70 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
votes
1answer
56 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
2answers
81 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
0answers
43 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 \...
3
votes
1answer
154 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 ...
2
votes
0answers
80 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 ...
2
votes
1answer
112 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\...
3
votes
2answers
123 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
votes
0answers
162 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$, ...
6
votes
0answers
133 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 ...
1
vote
0answers
50 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$-...
1
vote
0answers
36 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
0answers
59 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$ ...
7
votes
1answer
204 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 ...
5
votes
0answers
156 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 ...
0
votes
1answer
63 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 ...
2
votes
0answers
108 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 ...
2
votes
1answer
144 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 ...

1
2 3 4 5
9