Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
175
questions with no upvoted or accepted answers
10
votes
0
answers
156
views
Complexity class for probabilistic approximation algorithms with bounded error
What's the name of a complexity class of
optimization problems that have
"bounded error probabilistic approximation algorithms"?
Bounded error probabilistic version of APX
(as BPP is bounded error ...
- 560
8
votes
0
answers
198
views
Compute the expected size of an approximation of vertex cover
Consider the following randomized approximation algorithm of vertex cover:
Input: A graph G = (V, E).
Output: A set $C_G \subseteq V$ a vertex cover of $G$.
The algorithm:
Set $C_G := \emptyset$.
...
- 4,358
8
votes
0
answers
89
views
Connections between circuit complexity and Unique Games Conjecture?
Circuit complexity has connections to many questions in complexity theory.
For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
- 287
8
votes
0
answers
1k
views
Weighted Maximum 3-DIMENSIONAL-MATCHING with restricted weights (Approx Algo)
If the weights of the weighted 3-DIMENSIONAL-MATCHING problem are restricted to let's say, 1 and 2, is there a possibility to reduce this case to the unweighted 3-DIMENSIONAL-MATCHING problem?
(...
- 81
5
votes
0
answers
118
views
Minimum spanning tree and Hamiltonian path
For a graph $G(V,E)$, under what conditions is a minimum spanning tree of $G$ equal to a hamiltonian path on $G$?
IS there any body of literature connecting these two?
- 161
5
votes
0
answers
690
views
2 Dimensional Subset Sum: looking for information
I do not know if this problems exists with a different name, if it is, I could not find it.
The problem is this:
Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
- 111
5
votes
1
answer
117
views
A dynamic program to decide whether the solution is in a given range
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
The problem can be ...
- 5,844
4
votes
0
answers
67
views
Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph
I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible.
The problem is quite simple:
Given $G = (V, E)$ an undirected graph, ...
- 41
4
votes
0
answers
45
views
K-means, but normalized and with max
Given points $x_1, \ldots, x_n$ in the Euclidean space and $K \in \mathbb N$, I'm interested in the following objective.
Partition the points into $K$ clusters $C_1, \ldots, C_K$ so that:
$$\max_{i \...
- 315
4
votes
0
answers
36
views
What is a term for a problem that is hard to approximate within a factor $c$?
Let $f$ be a maximization problem. If there is a reduction from SAT to the following problem: "given an integer $c$, decide if there is an $x$ for which $f(x)\geq c$", then $f$ is NP-hard. ...
- 5,844
4
votes
0
answers
62
views
Universal approximation bounds of the form $\|f(x)-\hat{f}(x;w)\|\leq \varepsilon \|f(x)\|$
It is known that for every $\varepsilon>0$ there is an appropriate neural network architecture, such that one can approximate any continuous function $f:[0,1]^n\to[0,1]^m$ by the neural network ...
- 225
4
votes
0
answers
121
views
Approximation algorithms for indefinite quadratic form maximization with linear constraints
Consider the following program:
\begin{align}
\max_x ~& x^TQx
\\ \mbox{s.t.} ~& Ax \geq b
\end{align}
where $Q$ is a symmetric (possibly indefinite) matrix and the inequality is element-wise ...
- 168
4
votes
0
answers
67
views
Peculiar MCMC sampling problem
I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
- 41
4
votes
0
answers
65
views
Randomized algorithm to compute cover radius?
I am self-study the book "Geometric Approximation Algorithms" by Sariel Har-Peled. And I stuck on a problem and don't know how to start it.
Let $C$ and $P$ be two sets of point in the plane , such ...
- 153
4
votes
0
answers
104
views
Intuition for vertex/set cover approximation algorithms
The best approximation algorithm for vertex cover is randomly choosing an edge and removing its vertices (picking the largest degree vertex actually is a worse approximation), but the best ...
- 141
3
votes
0
answers
65
views
Approximation algorithm for minimal Covering of an orthogonal polyhedron
Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
- 63
3
votes
1
answer
259
views
Approximation factor preserving reduction
The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365:
Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving
...
- 143
3
votes
0
answers
35
views
Estimating number of points in 1D space
There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for ...
- 31
3
votes
0
answers
55
views
Approximate algorithms for class P problems
As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra ...
- 131
3
votes
0
answers
33
views
Rearrange items in order reduce fragmentation and reduce wasted space
I have a segment with some offsets at irregular intervals
There are items of various length inside. Items cannot be placed randomly. Instead, their left side must match some offset.
Items are free ...
- 131
3
votes
0
answers
164
views
Is there an optimization problem on planar graphs which is APX-hard ?
I'm looking for a optimization problem on planar graphs which is APX-hard, which means that it doesn't admit a PTAS (approximation scheme). It would be even better is the difficulty of the problem ...
- 356
3
votes
0
answers
176
views
Why gap preserving reduction is weaker than L-reduction?
In Vizirani's textbook says in page 332,
Gap preserving reductions are weaker than their L-reductions [...] one of the motivations for the PCP theorem was that establishing an inapproximability ...
- 729
3
votes
0
answers
236
views
2-approximation edge-cover algorithm using primal-dual method
The problem
Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle.
So far I managed to represent the ...
- 173
3
votes
0
answers
43
views
Incremental over-approximation of DAG reachability
I'm looking for a data structure that stores an approximation of a DAG:
If a node $x$ is reachable from a node $y$ in the DAG, then it is reachable in the approximation.
For a given fairly small root ...
- 161
3
votes
0
answers
335
views
Maximum Number of Edge Disjoint Paths of Length k in DAG
Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it?
...
- 31
3
votes
0
answers
173
views
Convex optimization with the help of Multiplicative Weights Update Method
I've already asked this question over at MathExchange, but since I received no replies or comments there, I hoped it might be more adequately fitting in this category.
I have a convex (concave) ...
- 31
3
votes
0
answers
87
views
Hardness of approximation for Disjoint Group Steiner Tree
Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group?
The (intuitive) ...
- 499
3
votes
0
answers
280
views
Approximation ratio of a greedy grid-cover algorithm
We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$.
Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
- 2,624
3
votes
1
answer
343
views
smaller size approximation to minimum vertex cover
Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum?
Usual algorithms seems to aim to find an approximation such that ...
- 61
3
votes
0
answers
86
views
What functions are easy to optimize?
Say I have variables $w_1, \dots w_n, h_1, \dots h_m \in \mathbb R$, constants $W, H$, functions $f_1, \dots f_k : \mathbb R\times\mathbb R\to\mathbb R$ from some family $F$ and for each function $f_i$...
- 3,627
3
votes
1
answer
62
views
Packing unsplittable flows problem
For a single stream of elements as input every elements should be routed into a fixed number of $k$ output streams trying to keep them balanced. In the following example $k=3$ :
Let's define as flow ...
- 131
2
votes
0
answers
82
views
Finding a maximum induced DAG in a digraph
I have a digraph D on n vertices formed in the following manner:
I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more ...
- 71
2
votes
0
answers
44
views
Designing Shortest Route
Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
- 43
2
votes
0
answers
40
views
State of the art implementations of minimum-cost multicommodity flow approximation algorithms
I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
- 165
2
votes
0
answers
43
views
Optimal allocation of heterogeneous divisible goods
In the context of my PhD on the simulation of the labor market with a multi-agent model, I encoutered a problem that doesn't seem to be really treated in the litterature, according to my searches on ...
- 31
2
votes
0
answers
58
views
An approximation variant of the halting problem
It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable.
I have just thought of a variant approximation-...
- 11.4k
2
votes
0
answers
63
views
Total weight of all spanning trees
Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
- 141
2
votes
0
answers
50
views
Complexity of approximating a function value using queries
I am looking for information on problems of the following kind.
There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
- 5,844
2
votes
0
answers
184
views
PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks
Consider the following problem:
We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...
- 113
2
votes
0
answers
40
views
FPTAS algorithm to find flow at each link for multi commodity flow problem?
Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
- 23
2
votes
0
answers
43
views
ln(n) + 1 Approximation for Set Cover constructions
Set Cover Problem: Given a set $X$ and a collection of subsets $S_1, S_2, \ldots S_m \subseteq S$, we want to find the smallest cardinality of a set of $k$ elements $\{i_1, \ldots i_k \}$ such that $\...
- 123
2
votes
0
answers
136
views
Relaxations for MILP with logical constraints
I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
- 121
2
votes
0
answers
87
views
Different properties of Heavy-Hitters and Count-Min Sketch algorithms?
I'm currently using the Heavy-Hitters algorithm as described here and I'm wondering what if any space, time, accuracy, or real-world performance differences I would see if I were to switch to an ...
- 251
2
votes
0
answers
113
views
An approximation for the sum of k largest elements of n-sorted arrays?
Suppose we want to find the sum of the $k$ largest elements of $n$-sorted arrays. All arrays are containing $k$ elements.
All elements are between 0 and 1, and the the sum of all elements in array $i$...
- 367
2
votes
0
answers
57
views
Hardness of approximation for online algorithms
Similar to the theory of hardness of approximation for (offline) approximation algorithms, has there been any work done on proving hardness guarantees for online algorithms? Theoretical lower bounds ...
- 133
2
votes
0
answers
526
views
Why is there no FPTAS for the maximum independent set problem?
I want to prove that the NP-hardness of Maximum Independent Set implies that there is no FPTAS for the Maximum Independent Set problem unless $P=NP$.
I found the following approach after some ...
- 427
2
votes
0
answers
40
views
Is it correct to say that there are similarities between CORDIC and digit recurrence algorithm for division?
I've been studying recently some variations of the CORDIC, and it seems to me that the logic behind at least the basic cordic or the redundant CORDIC is very similar to the logic used to design digit ...
- 693
2
votes
0
answers
64
views
Why this set cover greedy-like algorithm is not $\log k$-approximation for bin packing problem?
Bin packing: Given a set of $k$ items where item $j$ has size $s_j$ and a set of bins of capacity $C$ each. Use the minimum number of bins to pack all items while respecting the capacity of the used ...
- 259
2
votes
0
answers
131
views
Is this contradiction ? uniform hypergraph maximum matching has no constant factor approximation but it is bounded by minimum vertex cover
I have been so confused for a while!! Please help me with this, thank you very much in advance!!
Given hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $...
- 325
2
votes
0
answers
315
views
Is Max-2SAT with exactly 3 occurrences per variable APX-hard?
The Max-2SAT problem asks if at least k clauses of a 2CNF formula can be satisfied.
The Max-2SAT(at-most-3) problem is the restriction in which every variable occurs in
at most 3 clauses (counting ...
- 530