# Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

471 questions
Filter by
Sorted by
Tagged with
37 views

### Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?

Most problems about cutting graphs into roughly equal parts such as Sparsest cut, Graph partition, Balanced Cut, etc are based on minimizing the size of an edge cut. Even if all of those problems are ...
1 vote
49 views

### Find the minimum cost spider joining a root to some leaves

A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider. I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
• 567
1 vote
101 views

### Which is the most efficient of the two following approximation algorithms?

Let $\mathfrak{B}$ be a set, which will be called the set of bins. Suppose we have five maps \begin{align*} \mathrm{Value} &: \mathfrak{B} \to \mathbb{R} \\ \mathrm{Upper} &: \mathfrak{B}...
• 111
1 vote
52 views

### The tree augmentation problem, but with hyperlinks

In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
• 567
105 views

### Approximate inclusion-Exclusion?

I am trying to understand or find literature on the following problem of approximate inclusion exclusion. Let $S:=\{A_i\}_{i=1}^{m}$ be a set of $m$ sets. Every intersection of $k$ elements in $S$ ...
• 704
78 views

### Is there FPT or XP algorithms known for Shortest Steiner cycle and $(a,b)$-Steiner path problem

Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems. The Shortest Steiner cycle problem is defined ...
131 views

• 57
66 views

### Does the Christofides algorithm ensure this inequality?

Let $(X,d)$ be a finite metric space. Let $C$ be a Hamiltonian cycle (over $X$) outputted by Christofide's algorithm. Also, let $K$ be a minimum spanning tree. I am aware that Christofide's algorithm ...
31 views

### Multi-dimensional 0-1 Knapsack problem with a high number of dimensions

I would like to solve a multi-dimensional 0-1 Knapsack problem, by looking for approximation algorithms with constant approximation ratio if possible. Here the particularity is that the number of ...
• 101
175 views

### Maximize a special monotone submodular function - is it easier?

I am looking for a way to optimize the function $f$, defined below. First, fix some positive integer $k$ and let $c_1$ and $c_2$ be non-negative vectors in $\mathbb{R}^n$. Let $g$ be an increasing ...
• 567
43 views

### Online assignment lower bound results

I am reading the following paper which presents a $(1-\epsilon)$-competitive online algorithm for the MaxMin (similar to the makespan) problem, defined as follows: a set of requests are arriving in an ...
150 views

### Another variation of $k$-means problem in the plane

According to wikipedia, consider $k$-means problem in the plane : k-means clustering aims to partition the $n$ observations into $k (≤ n)$ sets $S = \{S_1, S_2, \dots, S_k\}$ so as to minimize the ...
• 23
47 views

### Existing results around approximation of minimum 2-edge connected Steiner subgraph

Problem $1$: minimum 2-edge connected subgraph We are given a $2$-edge connected undirected graph $G(V,E)$, and we are asked to find a $\textit{spanning}$ subgraph $H$, with minimum number of edges, ...
219 views

### Maximum Vertex Cover

I recently encountered the following exam problem: Given an undirected graph $G := (V,E)$ and a natural number $k \geq 1$, we want to cover as many edges as possible using exactly $k$ vertices. ...
38 views

1 vote
47 views

• 567
310 views

### Partition a graph into two clusters

Suppose given a complete weighted graph $G=(V,E)$, with positive weight. Are there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized? ...
• 194
214 views

### Finding top-K items in a sliding window

Imagine we have a stream of bank transactions. Each transaction has a target account and some amount of money. I'd like to find top K accounts over some period of time (e.g. last 7 days) which ...
• 223
47 views

### Using bin-packing algorithms to approximate maximum-makespan

Bin-packing (BP) and maximum-makespan (MM) are dual problems. In both problems, the input can be defined as a set $S$ of positive integers, and the output is a partition of $S$. In BP, there is a ...
• 1,826
161 views

### Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

Often, we can model combinatorial optimization problems with an Integer Program. Then there is an associated Linear Relaxation which drops the integrality constraints on the variables. Let's say we ...
• 567
89 views

• 267
238 views

### $\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

I am currently stuck on Exercise 5.12 in this book, which is apparently an unpublished result of David P. Williamson according to the book notes. The problem asks to use randomized rounding and first ...
• 680
330 views

### Is there any Bi-criteria PTAS for Metric $k$-Median?

The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the ...
• 1,389
315 views

### Find research partner (profession and beginner)

I've 10 years of industrial work, but in my free time, I do research, write papers to conferences, help to teach to my old friend at the university and I even did a Ph.D. full-time program. Now, I've ...
• 45
126 views

### Do there exist two equivalent objective functions one of which can be approximated but another one cannot?

I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
124 views

### Incorrect Lower Bound of k-Means++ Algorithm

The $k$-means++ algorithm is composed of two parts: Initialization part: the initial $k$ centers are chosen based on $D^2$ sampling. Expectation maximization part: the standard $k$-means algorithm (...
• 1,389
111 views

### Approximating Independent Dominating set on bipartite graphs

I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices. My question is: are there any positive results in the ...
• 266
1 vote
217 views

### Two valued variant of subset sum problem

I'm interested in the complexity of the following problem: Given a multiset $S$ containing only two positive integers $a$ and $b$, find a $k$-partition of $S$ that maximizes the sum of part with ...
70 views

### Is there a name for approximation algorithms with $f(OPT)$ approximation factor?

I have read that there are approximation algorithms with two different kinds of approximation factors: $c$ . A constant approximation factor. $f(n)$ . An approximation factor that is function of the ...
154 views

### Improving the approximation in Stockmeyer's counting theorem

Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that \left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
• 153
142 views

### Minimum Degree Spanning Tree Without Restricting Vertices Searched

This is reposted from cs.stackexchange. I asked the question more than two weeks ago and got no answers, so I thought to repost here. I am currently self studying approximation algorithms from The ...
• 680
1 vote
62 views

• 9,378