Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
514
questions
1
vote
1
answer
237
views
The Complexity of Multi-Objective Optimization
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
- 67
0
votes
0
answers
91
views
Complexity of the distance between the average vector of two subsets
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors, where $v_i\in \mathbb{R}^d$ is a vector, the target is to select two subsets $V_1=\{v_j\}_{j=1}^{|V_1|} \subset V$ and $V_2=\{v_k\}_{k=1}^{|V_2|...
- 67
0
votes
0
answers
70
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 ...
- 141
0
votes
0
answers
41
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 ...
- 113
2
votes
1
answer
205
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 ...
- 607
3
votes
0
answers
49
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 ...
- 31
2
votes
1
answer
162
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
2
votes
0
answers
55
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, ...
- 141
4
votes
2
answers
246
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. ...
- 89
2
votes
0
answers
48
views
Is logarithmic additive approximation to bin covering possible?
For the bin packing problem, the Karmarkar-Karp algorithm (1982) finds in polynomial time a packing with $OPT+O(\log^2(OPT))$ bins, and this was recently improved by Hoberg and Rothvoss (2017) to $OPT+...
- 2,078
1
vote
1
answer
190
views
2-Center problem with forbidden pairs
Is there a nearly linear-time 2-approximation (or $O(1)$-approximation) algorithm for the following problem?
2-Center with Forbidden Pairs
input: Bipartite graph $G=(V,E)$ where each vertex $v$ is a ...
- 194
5
votes
1
answer
192
views
Hashing-based vs almost uniform sampling-based approximate counting
Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani [1] states:
For any $\varepsilon > 0$ there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula $f$ outputs ...
- 778
4
votes
1
answer
116
views
A counter example for the set mean objective
Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function
\begin{align}
cost(\mathcal{P},c) =...
- 265
0
votes
0
answers
174
views
Minimize Cumulative Cost on Topological Sort
We are given a n-vertex DAG $G=(V,E)$ and also given a cost function $c: V \rightarrow \Bbb N$.
Given a topological sort $S = v_1,v_2,...,v_n$, it has associated a sorting cost $S_c = \sum_{i=1}^{n} C(...
- 9
1
vote
0
answers
53
views
Approximate solution for maximum coverage problem with choice constraint
Suppose a sequence of sets $S_1,S_2,...,S_i$ where each set contains sets of elements. That is, each set $S$ contains many sets $a_1,a_2,...,a_{|S|}$. We are given an integer $k$ and we assume that $\...
user53330
3
votes
0
answers
160
views
Bin packing where each item must occur in $k$ bins
I am looking for information on a generalization of bin-packing in which each item should appear in exactly $k$ different bins, for some positive integer $k$. The standard bin packing problem ...
- 2,078
0
votes
0
answers
51
views
Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?
The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph.
It seems like these problems would fall under the framework of network design problems (...
- 607
0
votes
0
answers
71
views
k-Median Problem With Restricted Centers
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,531
1
vote
1
answer
370
views
State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson
I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia:
The polynomial-time approximation algorithm for Max-Cut with the best
known ...
- 173
2
votes
1
answer
125
views
Can this special case of Node Weighted Steiner Tree be solved in polynomial time?
Consider the node-weighted steiner problem:
Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$.
Output: a minimum weight subset $S \...
- 607
0
votes
2
answers
360
views
Partition a graph into two clusters
Suppose given a complete weighted graph $G=(V,E)$, Is 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?
Note that, heaviest edge ...
- 194
0
votes
2
answers
308
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 ...
- 233
0
votes
0
answers
58
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 ...
- 2,078
0
votes
1
answer
220
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 ...
- 607
0
votes
0
answers
104
views
Examples of SDP constant approximation algorithms on minimisation problems
I was recently going through a survey on semidefinite programming and its use in approximation algorithms. Here are some problems I am familiar with that have SDP approximations:
Max Cut ($\approx 0....
- 1,088
1
vote
0
answers
52
views
Failing to understand a lemma regarding Robust Low Rank Approximation
I am reading Low Rank Approximation in the Presence of
Outliers by Bhaskara and Kumar and kind of stuck at the proof of Lemma 9. The paper studies robust (to outliers) low rank approximation problem. ...
- 265
1
vote
0
answers
42
views
Modifying sets to minimize the distance among each pair of the mean value of sets
Given $n$ points, each point $x_i$ has a value $v_i \in \mathbb{R}^{d}$, and there are $m$ point sets $\{S_1,\dots, S_m\}$ that each point set consists of some points. The size of point sets can be ...
- 67
0
votes
1
answer
62
views
Set cover where consecutive sets differ by at most one item [closed]
First I define my version of the set cover problem: We have a collection of sets such as $S_1, \dots, S_m$ where each $S_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of ...
- 230
1
vote
0
answers
48
views
A variant of k-median clustering
Suppose $\mathcal{P} =\{P_1,\cdots,P_n\}$ is a family of $n$ finite sets in $\mathbb{R}^d$. Given set $C=\{c_1,\cdots,c_k\}$ of $k$ points, consider the follwoing objective funtion
$cost(\mathcal{P},C)...
- 265
5
votes
1
answer
256
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 ...
- 1,088
3
votes
2
answers
492
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,531
-2
votes
1
answer
327
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
2
votes
1
answer
136
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 ...
user53330
3
votes
0
answers
158
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,531
3
votes
1
answer
137
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 ...
- 701
1
vote
2
answers
295
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 ...
- 25
2
votes
0
answers
76
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 ...
- 69
4
votes
0
answers
275
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
\begin{equation}
\left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
- 173
0
votes
1
answer
162
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 ...
- 1,088
1
vote
1
answer
69
views
What is the run-time of the bin packing approximation algorithm?
The best approximation algorithm that I found for the bin packing problem is by Hoberg and Rothvoss (SODA, 2017). In their Theorem 1.2, they mention that their algorithm finds a solution with at most $...
- 2,078
10
votes
1
answer
444
views
Is subtractive dithering the optimal algorithm for sending a real number using one bit?
Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner.
We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
- 9,438
3
votes
0
answers
162
views
Hessian of non differentiable convex function
The motivation of the question is the following:
Let $P$ be a set of $n$ points in $\mathbb{R}^d$. Consider the following objective(convex and differentiable) function $f:\mathbb{R}^d\rightarrow [0,\...
- 265
0
votes
1
answer
332
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,078
2
votes
1
answer
204
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.
- 607
1
vote
0
answers
37
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 ...
- 33
1
vote
1
answer
79
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 ...
- 475
0
votes
0
answers
122
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 ...
- 153
2
votes
0
answers
110
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 ...
- 101
7
votes
0
answers
98
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., ...
- 342
1
vote
0
answers
73
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 ...
- 186