Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
1
vote
0answers
32 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
29 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
53 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
32 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
29 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
43 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
47 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
40 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
34 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
19 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
27 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
192 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
50 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
53 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
56 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
51 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
38 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
82 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
84 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
54 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
44 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)
$...
3
votes
1answer
157 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
94 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
37 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
44 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
72 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
74 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
20 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
81 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
32 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
147 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
122 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
36 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
0answers
170 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
45 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
46 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
106 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 ...
1
vote
1answer
34 views
Variant of an approximation algorithm for vertex cover
Here is an approximation algorithm that finds vertex cover of a graph.
...
3
votes
1answer
203 views
Christofides algorithm (by hand)
I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[![enter image description here][1]][1]
...
0
votes
0answers
20 views
Converting an approximate algorithm for the minimization to the maximization form
I have a $\rho$-approximate algorithm for a minimization algorithm, where the objective is to minimize $O$ ($\rho \geq 1$ is some constant), such that the algorithm's solution is always within $\rho$ ...
1
vote
1answer
31 views
About a pre-processing step for primal-dual weighted set cover problem
I was reading the paper titled "Primal-dual RNC approximation algorithms" by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1.
They present a dual fitting based algorithm ...
1
vote
1answer
27 views
The notion of PAC in approximation algorithms
In computational machine learning, the notion of Probably Approximately Correct means that (generally speaking) we can find (or "learn") with a high probability a function which has "low error".
Is ...
1
vote
1answer
36 views
Knapsack-like problem oriented on contiguous selection
Problem inputs is an ordered array $A = [a_1, a_2, \ldots, a_n]$ with $\text{weight}(a_i) = w_i$.
We define a $subgroup$ of $A$, denoted by $B$, whose elements' indices are continuous in integer. For ...
2
votes
0answers
46 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 ...
1
vote
0answers
45 views
$k$ -center with outliers - but the points are on a line
The classic $k$-center with outliers problem is NP-hard and there exist approximation algorithms to solve it.
However, what if we assume that the input point are on a line, rather than in an ...
