Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
494
questions
0
votes
1answer
98 views
How to determine the approximation factor for greedy vertex cover algorithm?
The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $0$ are left.
Formally:
$\text{GreedyVertexCover}...
1
vote
1answer
23 views
Hitting set approximation
I'm having a small problem understanding what is the result of the 4-approximation polynomial-time algorithm for 4-Hitting Set.
What I mean is that by solving 4-Hitting set I get a group X such that ...
1
vote
1answer
18 views
Trouble to understand the proof of greedy algorithm for set cover
Problem definition: Given a universe $U$ of $n$ elements, a collection of subsets of $U$, $S = \{S_1,..., S_k\}$, and a cost function $c: S \to Q^{+}$. Find a minimum cost subcollection of $S$ that ...
0
votes
0answers
52 views
Approximate FPT and Approximate kernel for a decidable problem
I'm trying to prove the following:
For every decidable parameterized problem Π, Π admits a fixed parameter tractable α-approximation algorithm if and only if Π has an α-approximate kernel.
I'm trying ...
0
votes
0answers
40 views
Connection between planar graph and vertex cover
I have two similar problems in which I'm trying to find a connection to help me solve one of them.
In the first one I'm given a graph G = (V,E) , integer k, and vertex cover U of size k.
The objective ...
2
votes
1answer
16 views
Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time
I am trying to understand this paper, in which (k, b)-clusterability is defined like so:
A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ ...
2
votes
2answers
34 views
Approximate duplicate sampling from a stream
The following question (in two parts) comes from a homework sheet of the fall 2019 semester cs170 course taught at UC Berkely taught by professors Vazerani and Tal.
Design an algorithm that takes in ...
0
votes
1answer
24 views
Prove that the greedy algorithm for the minimum edge cover problem is 2-approximation
As said, I had to prove that the greedy algorithm:
Initialize $C = ∅$
Look for an un-covered vertex and add one of its edges to $C$
Repeat 2 while there's uncovered vertices
Is a 2-approximation ...
2
votes
0answers
23 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 ...
1
vote
2answers
43 views
Difference Between k-center and k-mean/median
I know that k-mean/median is to find a set $F$ that minimize
$$\sum_{i\in C}\min_{j \in F} d(i,j)$$
Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance).
...
4
votes
2answers
35 views
How do you express a floor / ceiling in the approximation factor of an approximation algorithm?
Intuitively I feel like this is a bit of a dumb question, and is probably related to my vague understanding of approximation algorithms and whatnot.
Suppose I have some minimisation problem $X$ where, ...
3
votes
1answer
30 views
Approximation of rational sequences via linear recurrences of small order
I wish to approximate a sequence of rational numbers using a linear recurrence of order $k$ for some small $k$ (preferably as small as possible). The Berlekamp-Massey algorithm solves the exact ...
1
vote
1answer
35 views
Proof of approximation ratio for approximate triangle inequality version of k-center
Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
0
votes
0answers
20 views
Dominating set in a connected graph
I have a synchronic ring network with $n$ (i.e. the nodes are connected in a ring), and I need a good approximation (factor of 3/2 of the optimal value) for the minimal dominating set.
I also need ...
1
vote
1answer
37 views
Communication complexity of equality gap problem
I'm interested to know what is the biggest known $0\le \epsilon\le 1$ such that the $gap-EQUALITY$ problem that is defined by:
$$f_\text{GEQ}(x,y)=\cases{1&$x=y$\\0 & $x$ and $y$ differ in at ...
1
vote
1answer
32 views
Inapproximability of graph problems on a restricted setting
I am considering the following problem $\mathcal{P}$.
$\mathcal{P}$: Given an undirected graph $G$, and an integer $k$, find a set of vertices $S \subseteq V(G)$, with $|S| = k$, such that the number ...
2
votes
1answer
78 views
Is there an FPTAS for 3-way number partitioning?
The maximization problem of the 3-way number partitioning reads as follows:
given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
1
vote
0answers
34 views
Hardness of multiplicative vs. additive approximation
Chlebik and Chlebikova prove that the problem "maximum 3-dimensional matching" is NP-hard to approximate within a multiplicative factor of $95/94$.
This means that, unless $P=NP$, there is ...
4
votes
0answers
32 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. ...
2
votes
0answers
45 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-...
4
votes
0answers
59 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 ...
2
votes
1answer
67 views
$\epsilon$-approximation Sub-linear time monotonicity testing
I have the following exercise I have been staring at for several hours to no avail.
Question:
Testing the monotonicity of a function - the case of bits: Given a function $f: [n] \rightarrow \{0,1\}$ ...
0
votes
0answers
33 views
maximal independent set on grid-based graph proof of approximation ratio
We have a G = (V, E, w), in form of a grid graph with a single diagonal line in each grid in form of below. Where w is the V weight.
We use a greedy algorithm that takes in each step maximum weighted ...
0
votes
1answer
24 views
maximal independent set on grid graph proof
I'm trying to figure out proof of maximum independent set from: this link. (1b part).
And I'm bit confused why exactly sum of $w(v)$ is less than or equal to sum of $w(v')$.
Shouldn't it be other way ...
1
vote
1answer
52 views
k-polynomial time approximation algorithm for set cover (k = max size of subsets)
Problem Definition: Given a universe set $U = \{1, 2, \dots, n\}$ and a collection of $m$ subsets $S_1, S_2, \dots S_m \subseteq U$, find the minimum collection of subsets that cover $U$.
I am ...
1
vote
1answer
33 views
Reduction from TSP to ATSP does not imply constant factor approximation algorithm
As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am ...
1
vote
0answers
42 views
The correct way to calculate the performance of my approximate algorithm
I've got a question about how best to classify the performance of an approximate algorithm. I'm trying to find the 'correct' value of a graph problem instance whose cost function has an objective ...
1
vote
1answer
22 views
Can PTAS $\epsilon$ parameter be dependent on the algorithm input?
Let A be a PTAS algorithm with time complexity $O\left(\frac{1}{\epsilon}\right)$.
Let $n$ be the input of the algorithm A.
From Wikipedia:
The running time of a PTAS is required to be polynomial in $...
0
votes
1answer
27 views
How are matchings a lower bound for an approximate vertex cover?
I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.
They mention that the 2-approximation ratio is a lower bound. How is a maximal matching ...
1
vote
0answers
31 views
Polynomial variable of inapproximability after reduction
I proved the inapproximability of a problem that, given a multigraph $G = (V, E)$ and a set of vertices $U \subseteq V$ tries to maximize a score $f(U)$ whose value depends on the edges of the graph, ...
-1
votes
2answers
19 views
Can you have an approximation that is higher than the optimal for a maximum value and a lower than the optimal for a minimum value?
I was reading this page on approximation ratios and the author says that for a problem looking for a:
maximum, an approximation algorithm will give us a value lower than this optimal maximum
minimum, ...
1
vote
1answer
22 views
Are disjoint edges the same as matchings?
I am reading Chapter 9 Approximation Algorithms of Dasgupts et al.'s Algorithm book for vertex cover approximation and they bring up the concept of matchings.
To support this, I am also watching ...
2
votes
1answer
109 views
Where does 1.3606 approximation ratio come from for vertex cover approximation?
I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm.
Later, the professor asks if we can do any better. The lecturer went on to say that ...
2
votes
2answers
86 views
Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
2
votes
1answer
45 views
k-center problem: proof for Gon algorithm gives a 2-approximation
The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following ...
-1
votes
1answer
59 views
Clique is NP hard to approximate up to $n^{a}$ for some $a \in (0,1)$
Given that
$\mathsf{NP}=\mathsf{PCP}_{[\frac{1}{n},1]}\left(O\left(\log n\right),\left(O(\log n\right)\right)$,
show that it is NP-hard to approximate clique up to factor of $n^a$ for some $a \in (0,1)...
1
vote
1answer
27 views
Online approximation algorithm for median?
Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c_1,c_2,c_3,\dots$?
The scenario is: I have a ...
1
vote
0answers
30 views
Cover a surface with disks of various size
I'm trying to find a cover of a surface using disks of variable sizes.
In the image, I want to cover the entire blue surface. The disks can go "out" of the blue surface and into the red part,...
0
votes
0answers
31 views
Is there an approximation algorithm for the three-person stable roommates problem?
While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", ...
1
vote
0answers
136 views
Minimum Degree Spanning Tree Without Restricting Vertices Searched [closed]
I am currently self studying approximation algorithms from The Design of Approximation Algorithms (Williamson and Schmoys; page 50 here), specifically the minimum-degree spanning trees (MDST) problem. ...
2
votes
1answer
52 views
Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time
I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. ...
0
votes
0answers
42 views
Most popular path in weighted cylic directed graph
Context
I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = ...
1
vote
1answer
102 views
Approximate max weight path in directed graph
Context
This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights ...
2
votes
2answers
129 views
Approximation of Set Cover
I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better ...
2
votes
2answers
45 views
Prerequisites for studying parametrized complexity
Which areas of CS/Math should one have mastered before diving into parametrized complexity?
0
votes
6answers
270 views
What algorithm do computers use to compute the square root of a number?
What algorithm do computers use to compute the square root of a number ?
EDIT
It seems there is a similar question here:
Finding square root without division and initial guess
But I like the answers ...
1
vote
1answer
50 views
Find The “Best” Permutation of Inputs to Maximize Sum of Functions (or approximate “best”)
The Problem (in words)
I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the ...
0
votes
0answers
18 views
Best algorithm / method to determine path length from noisy GPS points
i am analyzing a series of GPS points (with time stamps) which are noisy meaning have an accuracy of about 15 meter radius (sometime even more), and i need to extrapolate the distance the vehicle has ...
2
votes
1answer
55 views
2-Approximation algorithm for for messages across a cyclic network
Question
There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) ...
1
vote
0answers
17 views
Additive approximation to bin packing
The bin packing problem is an NP-hard optimization problem that has many constant-factor approximation algorithms. I am looking for an additive approximation. I.e., given a set $I$ of items and bin ...
