Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
577
questions
2
votes
1
answer
50
views
Uncapacitated facility location problem using local search
I'm studying about UFLP using the book The Design of Approximation Algorithms Ch 9 starting page 233 (there is an electronic free edition), I ran into some unclear steps in the book and need some help ...
- 23
1
vote
1
answer
134
views
Approximation algorithm question, clustering on n points
So the algorithm I thought of, is to iterate through the n points, centering a ball at each point, and keeping track of the point where we centered that encapsulated the most points. Then remove the ...
- 85
0
votes
0
answers
47
views
Applying Polynomial Time Approximation Scheme (PTAS) on an Algorithm
I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-ϵ) and (1+ ϵ) in the running time of the algorithm but I don’t ...
- 251
5
votes
5
answers
460
views
fast and stable x * tanh(log1pexp(x)) computation
$$f(x) = x \tanh(\log(1 + e^x))$$
The function (mish activation) can be easily implemented using a stable log1pexp without any significant loss of precision. Unfortunately, this is computationally ...
- 275
1
vote
1
answer
65
views
Variant of greedy algorithm for vertex cover
Does the following approximation algorithm for vertex cover also have an approximation ratio of 2? Why? Why not?
Input: $G = (V,E)$
Set $C \gets \emptyset$ and $E' \gets E$.
while $E' \neq \emptyset$...
- 11
2
votes
1
answer
384
views
Greedy algorithm for job scheduling
Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime.
How to prove that this algorithm has an approximation ratio of ...
1
vote
0
answers
44
views
Longest processing time rule on unrelated machines
I am trying to solve the job secheduling problem using the Longest processing time rule, that is: We seek to minimize the makespan by first sorting the jobs in decreasing order of processing time, ...
- 11
3
votes
1
answer
356
views
Maximum coverage 1/2-approximation algorithm: why does the central lemma hold?
I am looking for an approximation algorithm for the Maximum Coverage problem and a proof of its approximation ratio. As approximation algorithm I use the greedy algorithm which chooses the set that ...
- 33
1
vote
1
answer
737
views
Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > $0
Suppose you have a system that consists of $m$ slow machines and $k$ fast machines. The fast machines can perform twice as much work per unit time as the slow machines. Now you are given a set of n ...
- 11
1
vote
0
answers
38
views
Heuristic algorithm for the minimum weighted s-t cut with linear running time
To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $O(n^{2}\sqrt{m})$ time complexity. I'm interested in solving ...
- 253
0
votes
1
answer
53
views
Piecewise linear approximation for set of points
If we have a set of points $A$ and a known algorithm $Bestfit(A)$ to find
the best-fit straight line-segment through $A$, what would be a good algorithm to construct piece-wise linear segments (with ...
- 103
0
votes
3
answers
164
views
Numerical Approximation in Java
I am trying to solve an equation which I believe cannot be done analytically, but can use a numerical approximation to get a result. The equation is:
$$\frac{2*\sqrt{\pi}*h*s*e^{m^{2}/(2*s^2)}}{\sqrt{...
0
votes
0
answers
43
views
Approximation Set Covering Problem
I am studying approximation Set Covering problem, from "Introduction to Algorithms by Thomas H. Cormen" book. What I cannot understand is why they use harmonic numbers to the proof? What harmonic ...
- 125
1
vote
1
answer
32
views
3-Approximation for General position subset
I am currently studying for an exam and stumbled upon the following task:
Given the following problem:
Input A set of points $P \subseteq \mathcal{Q}^2$ and $k \in \mathbb{N}$
Question Find the ...
1
vote
0
answers
68
views
Minimum-cut with balanced and limited number of nodes in each partition: Does this have an efficient solution or even a name?
I'd like to remove the minimum number of edges from an undirected unweighted graph to partition the nodes into an arbitrary number of connected components $S_1$, $S_2$,$S_3$,... $S_k$ while maximizing ...
- 111
2
votes
0
answers
183
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
0
votes
1
answer
21
views
Compendium of approximation ratios, with narrower scope and more up to date than the NP-compendium?
I usually check the NP-compendium from Pierluigi Crescenzi, and Viggo Kann when I want to know the APX status and approximability results of a problem.
However, I understand that maintaining it is a ...
- 206
0
votes
2
answers
55
views
Calculating match % and ranking according to that
I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown ...
- 103
8
votes
0
answers
196
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
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
1
vote
1
answer
679
views
Derandomization of vertex cover algorithm
I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:
Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.
Add to ...
3
votes
1
answer
188
views
Integrality gap and LP-rounding
I have a doubt about integrality gap.
If I know that there is no integrality gap for a given problem, i.e.:
$$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$
...
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
0
votes
0
answers
72
views
Doubt on integrality gap and LP relaxation
I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-...
9
votes
1
answer
406
views
2D interval scheduling problem
Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
- 364
9
votes
2
answers
868
views
Prove that the 2-approximation of a modified local search algorithm for max-cut is tight
Consider the following local search approximation algorithm for the unweighted max cut problem:
start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you ...
- 113
2
votes
0
answers
42
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
5
votes
1
answer
209
views
Minimum edge weight k-exact cover with triangle inequality
Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$ satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$. Suppose $k \in \mathbb{N}$ (in ...
- 364
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
0
votes
0
answers
109
views
A heuristic for finding an edge cycle cover
I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph.
In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
- 101
1
vote
1
answer
177
views
Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem
The unweighted maximum coverage problem is defined as follows:
Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$.
Objective: find a subset $S' \subseteq S$ such ...
- 11
1
vote
1
answer
67
views
Reductions from non decision problems
I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min ...
- 222
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
32
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
1
vote
0
answers
39
views
Randomized version of the class $APX$?
Is there a class which is to APX what BPP is to P?
I'm looking for a definition that is like the following:
"For $r > 0$, an $r$-RPCA (randomized polynomial-time constant-factor approximation) ...
- 374
3
votes
1
answer
158
views
Optimal solution for Weighted points problem
Problem:
Fix a constant $k$. Given a set of $2d$-dimensional points $N = \{N_1, N_2, N_3, \dots, N_n\}$, each associated with an arbitrary weight, find a set of points $X = \{X_1, X_2, X_3, \dots, ...
- 77
3
votes
1
answer
100
views
About Steiner tree problem in graphs
In the
paper (p. 3)
and the
slides
presents the formulation of the Steiner problem on graphs
via so called Steiner cuts.
But according to the definition, the number of Steiner cuts and so the ...
- 131
3
votes
2
answers
628
views
Can non-metric TSP be approximated within some non-constant value?
It is known that metric TSP can be approximated within some constant value, such as 3/2 through Christofides' algorithm. It is also known that non-metric TSP cannot be approximated within some ...
- 675
0
votes
0
answers
155
views
What is the approximation for odd cycle transversal?
What is the best approximation for odd cycle transversal? (on general graphs)
Sorry if this is easily found everything I found about odd cycles is about paramaterized complexity and kernels
- 83
3
votes
1
answer
132
views
How to use c-gap problems to prove inapproximability?
Suppose there is a specific set function with some properties - $f=2^V\to \mathcal{R}$. It is known that the following problem is NP-Hard: Find $S\subseteq V, |S|\leq k$ such that $f(S)$ is maximized....
- 235
3
votes
1
answer
35
views
Hardness of approximation statement clarification?
In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved ...
- 61
0
votes
1
answer
605
views
Difference Between PTAS and FPTAS [duplicate]
According to this link:
Polynomial Time Approximation Scheme (PTAS) is a type of approximate
algorithms that provide user to control over accuracy which is a
desirable feature. These algorithms ...
- 205
3
votes
1
answer
192
views
Is this variation of set-cover NP-hard to approximate?
The classic set-cover problem is described as follows:
Let $S = \{s_1, ..., s_n\}$ be a target set, and let $\Lambda = \{A_1,
..., A_m: A_i \subset S\}$ be a collection of subsets of $S$. The
...
- 163
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
3
votes
0
answers
74
views
Alternative criterion for approximate maximum-weight perfect matching algorithms [closed]
Is there any literature on approximate maximum-weight perfect matchings where the approximation criterion is not the factor between the approximate and exact weight sum achieved by each solution, but ...
- 31
1
vote
1
answer
196
views
Analysis of an approximation claim
Consider the load balancing problem on two machines. Thus we want to distribute a set of $n$ jobs with processing times $t_1,...,t_n$ over two machines such that the makespan (maximum of the ...
- 140
1
vote
0
answers
47
views
An LP with two covering constraints - how to round
I came across an LP with two covering problems, and I wonder how to
find a good approximation. For the relevant part of the LP: We have
a set $E$ , for each $e\in E$ we have a corresponding set $Y_{e}\...
- 267
3
votes
1
answer
81
views
Non-existence of approximation algorithm for the knapsack problem
I am working on the following exercise: Prove that if $P \neq NP$, there cannot exist an approximation algorithm $A$ for the knapsack problem (KP) such that $\exists k \in \mathbb{N}, \forall I \in S: ...
- 31
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
0
votes
1
answer
93
views
What are the current state of art approximation algorithm for NP-Hard problems? [closed]
I came cross some works try to use deep learning to approximate NP-Hard
https://arxiv.org/pdf/1810.10659.pdf
Though the paper seems to have very good results but based on the citations. I'm quit ...
- 171