Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
415
questions
0
votes
1answer
35 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 ...
0
votes
0answers
39 views
A variant of the knapsack problem
Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
-1
votes
0answers
114 views
Number of executions of the algorithm with probability about graphs
Consider an undirected graph $G = (V, E)$ representing the social network of friendship/trust between
students. We would like to form teams of three students that know each other. The question
is to ...
8
votes
0answers
88 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$.
...
1
vote
1answer
536 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 ...
1
vote
1answer
57 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?)},$$
...
2
votes
0answers
32 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 ...
0
votes
0answers
56 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-...
8
votes
0answers
161 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{...
9
votes
2answers
177 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 ...
1
vote
0answers
17 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 $\...
4
votes
0answers
72 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 ...
0
votes
0answers
30 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-...
1
vote
0answers
57 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 ...
1
vote
1answer
26 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 ...
3
votes
0answers
33 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 ...
3
votes
0answers
23 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 ...
0
votes
0answers
11 views
What are some counter examples for Load balancing problem?
I learnt about load balancing problem under approximate algorithms. I am learning about it, and studying methods to counter part it's non -solvability under P time. I am quite out of my examples, and ...
1
vote
0answers
24 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) ...
3
votes
1answer
75 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, ...
1
vote
0answers
36 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 ...
1
vote
2answers
65 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 ...
0
votes
0answers
29 views
Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general
A greedy algorithm for finding a minimum feedback vertex set
is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
0
votes
0answers
34 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
0
votes
0answers
14 views
Algorithmic question: distribute balls, optimise for balancing (i) weights (ii) probabilities of picking balls
I have an algorithmic problem that requires some lengthy explanation, which follows below.
tl;dr: distribute balls with weights among bags, optimise for balancing both (i) the weights between the ...
2
votes
1answer
23 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....
3
votes
1answer
26 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 ...
0
votes
1answer
72 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 ...
3
votes
1answer
48 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
...
4
votes
0answers
60 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 ...
3
votes
0answers
53 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 ...
1
vote
1answer
54 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 ...
1
vote
0answers
40 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}\...
3
votes
1answer
31 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: ...
4
votes
0answers
56 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 ...
0
votes
1answer
43 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 ...
2
votes
1answer
41 views
Shortest hamiltonian path for different dimension points
The shortest Hamiltonian path (solution) for a set of points in $\mathbb{R}^k$ (in Euclidean space) changes subject to $k$.
For example if for $k=1$, the shortest Hamiltonian path will be the sorted ...
2
votes
1answer
52 views
What is an approximation factor for the Greedy Motif Search algorithm?
What is approximation factor for the Greedy Motif Search algorithm?
I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native ...
3
votes
1answer
59 views
Is there an algorithm to overapproximate a context free grammar by a regular expression?
I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
4
votes
1answer
70 views
MAXSAT approximation
We have been studying a 1/2-approximation for MAXSAT which runs in expected polynomial time, by randomly assigning True/False to each variable and repeating until we reach an assignment with at least ...
0
votes
0answers
61 views
Definition of unbounded approximation ratio
Suppose that there is a specific instance of a graph for which the approximation ratio of an algorithm polynomially increases with the number of nodes of the graph, say the approximation ratio is $n^2$...
0
votes
0answers
37 views
Weighted-Set Cover Approximation
So in the weighted-set cover problem, I need to determine the minimum weight cover. My algorithm calculates the efficiency for each set:
...
3
votes
1answer
38 views
Algorithm to pick elements in one array that sum to a setpoint, and corresponding elements in other array to average to a setpoint?
Note: The input file is an excel file. However, I am only looking for help with the algorithm as I can then code it in VBA.
I need to scan both columns (shown below) to find any number of column 1 ...
-1
votes
2answers
384 views
Vertex cover of bipartite graph
A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
A minimum vertex cover is a vertex cover with minimal cardinality.
From codeforces,
...
1
vote
0answers
42 views
Delivering to two or more locations in one go while respecting deadlines?
Assume that I have a business where people can place product orders. Each order must be delivered within a time limit, say $x$ minutes.
I need 15 minutes to make each product. However, multiple ...
3
votes
1answer
57 views
Clarification on NP-hardness and hardness of approximation results for set cover?
I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements.
I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it ...
2
votes
1answer
112 views
Approximation algorithm for weighted set cover, using multiplicative weights
It is known that the problem of fractional set cover
can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ...
1
vote
1answer
87 views
Approximation ratio of greedy algorithm for makespan
In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf
Lemma 5 is given as:
The approximation factor of the modified greedy [scheduling] algorithm is 4/3.
...
1
vote
1answer
81 views
Job scheduling approximation
In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf
Lemma 5 is given as:
The approximation factor of the modified greedy [scheduling] algorithm is 4/3....
0
votes
1answer
41 views
invariant of bin packing
We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We ...
