Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
212
questions with no upvoted or accepted answers
17
votes
0
answers
780
views
Practically Good Algorithms of a Very Low Computational Complexity Class
I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties:
1) Solving the ...
- 6,013
15
votes
0
answers
389
views
Complexity of approximating the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$
I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
- 3,950
14
votes
0
answers
615
views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
- 1,953
14
votes
1
answer
343
views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(...
- 838
12
votes
0
answers
364
views
How good is greedy in average?
Given a family ${\cal F}\subset 2^E$ of (feasible solutions),
the maximization problem on ${\cal F}$ is,
for every weighting $x:E\to \{0,1,\ldots\}$ of ground elements, to compute the maximum weight
...
- 6,685
10
votes
0
answers
296
views
Approximating a convex polyhedron, with fewer inequalities
I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words,
$$\mathcal{...
- 11.7k
9
votes
0
answers
276
views
Advances towards proving the Held-Karp conjecture for TSP
I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture.
The Held-Karp relaxation is conjectured to have an integrality gap of $\...
- 313
9
votes
0
answers
306
views
Additive error in counting the number of 1's in a sliding window?
The setting is as follows:
We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
- 9,438
8
votes
0
answers
111
views
Approximating a max-cut's intersection with other cuts
For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
- 181
8
votes
0
answers
225
views
Complexity and approximability of maximum edge biclique problem on co-comparability graphs
A subgraph $H$ of a given graph $G$ is called a biclique of $G$ if $H$ is a complete bipartite graph. Given a graph $G$, finding a maximum edge biclique is known to be NP-complete (Peeters, Discrete ...
8
votes
0
answers
177
views
Is the dominating set problem constant-factor-approximable in undirected path graphs?
I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class.
A graph is an undirected path graph if it is the vertex-intersection graph of a family of ...
- 2,143
8
votes
0
answers
366
views
Efficiently approximating derivative of a well-behaved function
I need an algorithm for adaptive sampling a well-behaved function and computing its derivative in the sampling range with prescribed accuracy. The function has no more than one minimum in the sampling ...
- 189
8
votes
0
answers
565
views
Difference between Primal Dual Algorithm for Proper and Uncrossable Functions
Williamson with many of his co-authors had worked on generalized primal dual algorithms on edge weighted graphs considering three types of functions:
(1) super-modular functions
(2) proper functions
...
- 725
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
7
votes
0
answers
119
views
Deterministic approximation algorithms for treewidth
As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee is randomized, and no deterministic approximation algorithm with this factor ...
- 3,256
7
votes
0
answers
266
views
Positive cut algorithm on bipartite graphs with negative weights
Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
- 71
7
votes
0
answers
230
views
Minimum weight expander
Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a ...
- 4,001
7
votes
0
answers
832
views
Approximation results for 3-partition
The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
- 951
7
votes
0
answers
697
views
Hardness of Approximation results for Special Set Packing Problem Wanted
Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem?
The general Set Packing Problem would be:
Given A Collection of ...
- 71
7
votes
0
answers
267
views
Results regarding Bounded Diameter Minimum Spanning Tree
Given edge weighted undirected graph the problem asks to output a spanning tree $T$ of minimum weight such that the path between any two vertices in the tree $T$ is bounded by the input $k$. One of ...
- 333
7
votes
0
answers
160
views
log(OPT) approximation for directed balanced vertex separator
Leighton, Rao presented an $O(\log n)$ approximation algorithm for directed and undirected balanced vertex separator. Agarwal, Charikar, Makarychev, Makarychev improved this approximation factor of ...
- 1,953
6
votes
0
answers
274
views
Techniques for solving huge linear programs
During the solution of some computational problem, we have arrived at a linear program of the following form:
\begin{align*}
\text{maximize} ~~ c x
\\
\text{subject to} ~~ A x \leq b, x \geq 0
\...
- 2,078
6
votes
0
answers
312
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
6
votes
0
answers
191
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
$$\...
- 271
6
votes
0
answers
181
views
Lower bound for Yao's algorithm on general addition chains?
An addition chain of size $n$ for given integers $n_1,n_2\dots ,n_p$ is a sequence of integers $k_1,k_2\dots ,k_n$ such that
$k_1=1$,
for all $i$ $(2\le i\le m)$ we have $k_i=k_j+k_m$ for some $1\le ...
- 500
6
votes
0
answers
182
views
Statistical Algorithms vs Convex Relaxations - Planted Clique
I am trying to understand exactly what the lower bounds for the query complexity of statistical algorithms imply for convex relaxations for the planted clique problem ?
A recent paper by Feldman, ...
- 666
6
votes
0
answers
401
views
Bipartite vertex separator
Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph?
I have a ...
- 211
6
votes
1
answer
244
views
Hardness of approximating chromatic number of triangle-free graphs
The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs.
Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?
- 1,443
5
votes
0
answers
78
views
A simultaneous FPTAS for both max-min and min-max number partitioning
The multiway number partitioning problem has two optimization variants: in one variant the goal is to minimize the largest bin sum (the "makespan"), and in the other variant the goal is to ...
- 2,078
5
votes
0
answers
93
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
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
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
5
votes
0
answers
226
views
Why is HyperLogLog (near-)optimal?
The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads:
Clearly, maintaining $\epsilon$-approximate counts till ...
- 329
5
votes
0
answers
211
views
On permanent of $\{\pm1,0\}$ matrices
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input.
Is ...
- 12.8k
5
votes
0
answers
214
views
Fast Approximation Algorithms for Covering Design
The covering design problem is as follows: We are given a universe $\mathcal{U}$ of size $n$. By $C(n,k,l)$ we denote the smallest cardinality of any set system $\mathcal{A} \subset 2^\mathcal{U}$ ...
- 143
5
votes
0
answers
247
views
Maximizing the number of selected edges with opposing requirements
Consider the following problem:
Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$.
Output: a subset of vertices $W$ of size $k$ which maximizes the ...
5
votes
0
answers
251
views
Is MAX-SAT SETH (like) hard?
If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy.
There ...
- 958
5
votes
0
answers
121
views
The distribution on the solution space induced by randomized rounding
Consider the Goemans-Williamson algorithm for the MAX-CUT problem.
It is known, that if $maxcut(G) \geq 1-\epsilon$, then
the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
- 1,224
5
votes
0
answers
112
views
Maximizing a submodular function with restricted values
Maximizing a general monotone submodular function $f$ under the constraint that $|S|\leq k$, can be approximated to $(1-1/e)$. I am wondering if a better approximation algorithm exists if the ...
5
votes
0
answers
483
views
Tuning Parameters of Locality Sensitive Hashing
We have given a set of $n$ binary vectors each of dimension $d$, i.e. a binary matrix of $d*n$. Our goal is to group vectors which are almost similar, $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ ...
- 639
5
votes
0
answers
375
views
Approximate c-chromatic number, each color class is P4-free (cograph)
The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
- 1,443
5
votes
0
answers
146
views
Approximation for accumulative set cover
Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\\{1,\ldots,m\\}$, I want to maximize the quantity
\begin{equation}
\sum_{k=...
- 1,026
5
votes
0
answers
179
views
Online Interval Coloring Problem
We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $...
- 1,591
5
votes
0
answers
246
views
On the optimal solution of the CKR formulation for MULTIWAY CUT
Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1]. Let $U_i$ be those vertices in $V-T$ which is ...
- 2,560
5
votes
0
answers
78
views
A question regarding Improved Algorithm for Degree Bounded Survivable Network Design Problem
In the paper "Improved Algorithm for Degree Bounded Survivable Network Design Problem", by N. Vishnoi and A Louis, have used the iterated rounding approach in a similar as by Jain in designing the ...
- 725
5
votes
0
answers
127
views
Finding an index set so that row sums are positive
Assume $A$ is a $n$-dimensional matrix of real numbers. The diagonal entries are non-negative, and all other entries are non-positive. I would like to find a subset $I \subseteq \{1, 2, \ldots n\}$ of ...
- 181
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
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
4
votes
0
answers
573
views
Hardness of Approximation for minimum path cover in an undirected graph?
Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path ...
- 53
4
votes
0
answers
123
views
Learning hidden variable distribution
Consider a set of $k$ continuous variables. Each variable $x_k$ is associated with a hidden distribution from which its value is sampled independently of other variables. I am given a set of ...
- 1,177