Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

Filter by
Sorted by
Tagged with
-2
votes
0answers
32 views

A $TM$ definition on approximation solutions to optimization problems

It looks like we are defining approximation solutions as a witness specifying program. We want to find a witness which agrees within some approximation of optimal. Is it possible to specify as '...
0
votes
0answers
37 views

Balanced and general $MAXkSAT$ known approximation results and bounds from $UGC$

$MAX2SAT$ has a $0.9401$ to $0.9402$ approximation algorithm which is conjectured to be optimal by $UGC$ while there is a balanced $MAX2SAT$ bound of $0.943$ approximation which is conjectured to be ...
-2
votes
0answers
54 views

Why does the ball growing procedure of Even etal [1998] not work for directed multicut?

Why does the ball growing procedure of Even etal [1998] "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs" not work for the directed multicut problem considered in e.g &...
9
votes
1answer
3k views

What's the approximation factor of this Max k-Cut approximation?

I'm thinking about an approximation algorithm for Max k-Cut. One simple and more involved approximation algorithms can be found here. The Max k-Cut problem is defined as follows. Input is a graph G = ...
0
votes
1answer
57 views

A k-approximation to k-way number partitioning

The $k$-way number partitioning problem accepts as input a multiset $S$ of positive numbers, and returns a partition of $S$ into $k$ subsets such that the subset sums are as nearly-equal as possible, ...
2
votes
1answer
114 views

Is this homework problem on T-joins wrong? [closed]

In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
1
vote
0answers
25 views

A continuum version of the 1D k-means clustering problem: constant factor approximations

Modify the k-means clustering problem in 1D by assuming that, instead of a finite number of observations, we must classify into $K$ clusters a continuum of observations, distributed on the unit ...
1
vote
1answer
34 views

Best approximations of Minimum Dominating Sets in chordal graphs

I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime ...
13
votes
0answers
365 views

Can we approximate the number of words accepted by an NFA?

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. In a related question, it was suggested that exact counting of the number of words accepted by $M$ is $\#P$-Complete. The second ...
0
votes
0answers
108 views

Algorithms and approximations for optimal offline binary tree operations

Let's say we are using a binary tree to represent a set of elements, with operations $\mathsf{insert}(x)$ and $\mathsf{delete}(x)$. We will assume that the operations are used such that a deleted ...
2
votes
0answers
90 views

Can hash functions speed up quantum simulation? (Generalizing May and Schlieper's idea) [closed]

To conform with the CS Theory SE crossposting rules, I've created a separate post for dequantizing Shor's algorithm (discussion on the Quantum Computing Stack Exchange was mostly about Shor's ...
7
votes
0answers
81 views

Jump number approximation algorithm

A linear extension $x_1 x_2 \ldots x_n$ of a partially ordered set (poset) is said to have $k$ jumps if there are $k$ occurrences of consecutive elements that are incomparable with each other -- i.e., ...
1
vote
0answers
64 views

Can the theory of Bidimensionality be applied to weighted instances of a problem?

So my understanding of bidimensionality is you are assured the problem solution is about O(k^2) so you can pay O(k) purely to reduce the instance to one of bounded treewidth. As far as I know, this ...
1
vote
0answers
54 views

polytime approximability of directed multicut

Does anyone know how well directed multicut can be approximated in planar and minor free graphs? Also any survey of approximability of directed multicut and multicut in various graph classes would be ...
12
votes
4answers
738 views

Approximation algorithms used in exact algorithms

Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms. However, constant factors are ignored in time complexity. So I wonder if ...
-1
votes
1answer
63 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
vote
2answers
101 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 ...
6
votes
1answer
131 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 ...
6
votes
1answer
150 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-...
0
votes
1answer
106 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 $...
9
votes
2answers
3k views

What are good approximation algorithms for the subset sum problem so far?

By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.
9
votes
1answer
336 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 ...
1
vote
0answers
65 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 ...
2
votes
1answer
84 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 ...
5
votes
1answer
125 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 ...
0
votes
0answers
33 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[...
6
votes
1answer
538 views

Maximizing difference of a submodular and a modular function

I'm considering a network planning problem which is stated as follows: From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that \begin{equation} f(\mathcal{A}) - \...
7
votes
1answer
570 views

Ordering of a DAG minimizing some definition of cost

Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i \mid \exists k>i: (v_j,v_k)\in A\...
1
vote
1answer
67 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
31 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
34 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
67 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 ...
6
votes
0answers
151 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 $$\...
-1
votes
1answer
61 views
0
votes
1answer
83 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, ...
11
votes
5answers
544 views

Submodular functions: reference request

I would be very much interested in references to the theory of submodular functions (from basics to advanced). In particular, I am studying approximations to hard optimization problems and I want to ...
2
votes
0answers
95 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
113 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
161 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
985 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
votes
5answers
558 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 ...
-1
votes
1answer
70 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
952 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
67 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,...
6
votes
1answer
236 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 ...
14
votes
1answer
371 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
220 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 ...
3
votes
2answers
191 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.
2
votes
1answer
145 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 ...
8
votes
1answer
472 views

Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature. ...

1
2 3 4 5
9