Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
392
questions
0
votes
0answers
8 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 ...
1
vote
1answer
8 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....
1
vote
1answer
10 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
14 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
33 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
58 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
36 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
22 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
34 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
30 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
54 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
36 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
33 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
47 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
49 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
47 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
38 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
21 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
30 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
237 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
52 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
65 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
61 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.
...
0
votes
1answer
52 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
39 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 ...
4
votes
2answers
90 views
Find maximal subgraph containing only nodes of degree 2 and 3
I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
0
votes
0answers
90 views
Show that for each even n, there exists a graph with n vertices, such that the 2-approx VC alg returns a VC which is exactly twice the Minimum-VC
Question: Show that for each even n, there exists a graph with n vertices, such that the ALG(algorithm) returns a vertex cover which is exactly twice the size of minimum vertex cover.
Define ALG: ...
3
votes
1answer
56 views
Find the smallest set of strings which “covers” a given set of strings (coverage = containing as substring)
Let $S$ be a finite set of strings and $0 < k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds:
$\forall t \in T(k,l): k \leq |t| \leq l$
$\...
0
votes
0answers
51 views
Knapsack approximation algorithm (weights scaling)
I am trying to prove the following Knapsack approximation algorithm, the problem definition:
Input:
A set $S$ of $n$ objects that contains weights and values:
$w_1,w_2,\ldots,w_n$ (weights)
$...
4
votes
1answer
198 views
Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$
The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so ...
1
vote
1answer
97 views
Is this partitioning problem NP-complete?
I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this ...
0
votes
1answer
40 views
Minimal edge cover of the hypergraph
We know that minimal edge cover for the normal graph is polynomial time solvable.
Is it also true for hypergraph?
0
votes
1answer
49 views
set cover to edge cover
I want to find set cover of this problem.
I have sets, each of cardinality 3. I want to find set cover.
This is what I am doing.
Treat each set as an edge, which is incident on each of its element.
I ...
0
votes
1answer
78 views
minimum cardinality maximal matching of graph
How to find minimum cardinality maximal matching?
I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.
2
votes
1answer
83 views
Longest-path in a graph, where the path should be 'straight'
Is there any existing work done on finding paths that are geometrically straight?
I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of ...
1
vote
1answer
21 views
Is there an FPRAS for the number of min st cuts in general graphs?
Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get ...
2
votes
1answer
83 views
Max flow and Matching problem
Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .
2
votes
0answers
36 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 ...
0
votes
0answers
17 views
Johnson-Lindenstrauss and k-means
I have a question about Johnson-Lindenstrauss and k-means.
I m study a resource that explain a link between Johnson-Lindenstrauss and k-means.
From what I understand, Johnson-Lindenstrauss helps us ...
1
vote
2answers
199 views
set cover where only certain special subsets are allowed
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...
1
vote
1answer
137 views
Vertex Cover approximation algorithm
I have an algorithm that solves the Vertex Cover problem. The algorithm is
Repeat while there is an edge:
Arbitrarily pick an uncovered edge $e = uv$ and add $u$ and $v$ to the solution. ...
2
votes
1answer
44 views
what is a shearlet/shearlet transform and how can i use it?
from what wikipedia says shearlet is a successor to wavelets(whatever that is) and that they are extremely good at representing complicated data efficiently. But neither wikipedia nor other articles ...
1
vote
1answer
16 views
Approximation factor shorthand clarification
I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation ...
3
votes
1answer
36 views
Determining a value in an algorithm on its first run
I was given the following algorithm as a solution to one of my problems.
However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never ...
1
vote
1answer
199 views
Proving there is no polynomial algorithm for independent set
I need some guidance in an assignment I'm doing.
I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ...
1
vote
0answers
34 views
Sort-of interval scheduling
The Problem
I have a set of sets of time intervals (hour, minute, day of the week). I want to select exactly one interval from each of set, and I want to minimize...
the number of pairwise ...
1
vote
1answer
53 views
Defining Gap Problems
I recently started studying about approximation problems in the complexity class that I'm taking. I feel like some of the definitions in this subject presented in my course and that I came across ...
1
vote
1answer
55 views
Amplification for Randomized Algorithms
I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms.
Amplification for randomized algorithms:
Given a randomized algorithm with time ...
4
votes
0answers
115 views
Maximum-minimum-satisfiability [closed]
In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the ...
