Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
507
questions
0
votes
0answers
34 views
An approximation algorithm for partitioning metric completed graph
Given complete metric weighted graph $G=(V,E)$ with $n$ vertices. Are there an algorithm that partition $G$ into to disjoint part $(C_1,C_2)$ that sum of heaviest edge $e\in C_1$ and heaviest edge $e'...
2
votes
1answer
50 views
Currently best approximation for graph coloring
As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation ...
0
votes
0answers
16 views
Is it possible to replace the softmax in the Nyströmformer?
My question is about the article Nyströmformer A Nyström-based Algorithm for Approximating Self-Attention.
and also about the $\alpha$-entmax $(\boldsymbol{z})=[(\alpha-1) \boldsymbol{z}-\tau \mathbf{...
0
votes
1answer
22 views
Failing to calculate the gradient and y-shift for best fit line using sum-squares method. Can anyone help me to pinpoint the issue?
I'm trying to work out how to make the working implementation of fitting the straight line among the set data points. I base my function:
...
1
vote
1answer
18 views
Textbook proofs for approximation algorithms for scheduling
I am planning to teach approximation algorithms for problems such as job scheduling and number partitioning. I would like to teach proofs, but the proofs I found in the original papers (e.g. this one) ...
1
vote
0answers
30 views
Approximation classes for optimization problems with real values
Question - Can an optimization problem $\mathcal{P}$ with a real-valued measure function $m_{\mathcal{P}}$ be in $NPO$ (please see definitions below), $APX$, etc.?
If my understanding is correct a ...
2
votes
0answers
52 views
Approximation algorithm for minimal Covering of an orthogonal polyhedron
Covering an orthogonal polygon with rectangles is according to Culberson and Reckhow NP-complete, even for the case without holes. Franzblau shows an 2-approximation algorithm for simple polygons for ...
0
votes
1answer
30 views
Differences between Polynomial and fully polynomial time approximation scheme
I have a confusion on understanding the relation between:
The input n
,The relative error and
The running time of the program In both PTAS and FPTAS.
In "The running time of PTAS must be ...
0
votes
1answer
28 views
Polynomial and fully polynomial time approximation scheme
How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program?
Is there any other way to decide?
1
vote
0answers
45 views
How is "expected approximation ratio" defined in cases when the expected value of the optimal solution is known?
Consider an approximation algorithm which does better than $f(n)$, in expectation. Suppose we know that $\mathbb{E}(OPT)=g(n)$.
Given that we use the convention of "larger divided by smaller"...
7
votes
1answer
98 views
What is the approximation ratio of this bin-backing algorithm?
Consider the following algorithm for bin packing:
Initially, sort the items by their size.
Put the largest item in a new bin.
Fill the bin with small items in ascending order of size, up to the ...
0
votes
0answers
34 views
Fast text comparison algorithm for long texts
I want to calculate a similarity ratio between two long texts (by "long", I imply something around 1000 characters or higher). For example, two texts with only one word changing should have ...
0
votes
0answers
15 views
Voice activation keywords algorithms on iot devices?
I've been scouting the internet for days and after a lot of digging, I decided to resort to my last hope and ask: I'm talking about the "hey Google", "Alexa" and so on voice ...
0
votes
1answer
106 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
24 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
54 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
42 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
19 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
35 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
33 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
27 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
44 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
31 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
39 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
39 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
88 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
35 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
47 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
72 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
34 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
25 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
54 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
35 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
24 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
28 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
113 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
89 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
49 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
60 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
34 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 ...
