Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
527
questions
0
votes
0answers
4 views
Proof that there isnt a c-additive approximation to Partition Problem
Define
Partition = { x1, x2, x3,....,xn| there is a division to two groups in which the sums of the two groups are equal}
is there a proof that there isnt an additive approximation algorithm to the ...
0
votes
0answers
12 views
Relationship between IID and Random Order Inputs
I am currently working on a project where we hope to find $(1-\epsilon)$ competitive ratio algorithms for an online problem (subject to certain largeness assumptions) in both the IID and random order ...
1
vote
0answers
35 views
Graph in which greedy algorithm for maximum matching is a 2-approximation
Here is a greedy algorithm for maximum bipartite matching:
Iteratively select an edge that is not incident to previously selected edges.
This algorithm returns a 2-approximation, and runs in linear ...
2
votes
2answers
83 views
Bin-packing with a capacity constraint on pairs of bins
In the classic bin-packing problem, we have to pack some positive integers into bins, such that the sum in each bin is at most some constant $B$, and subjet to this, the number of bins is minimum.
...
1
vote
0answers
32 views
Bisecting Intervals of floating point numbers containing 0 and infinity fairly
It is seldom considered that floating points are not evenly distributed in the real number line. I've been working with interval arithmetic and noticed when bisecting $[a,b]$ on the real number line ...
4
votes
0answers
38 views
K-means, but normalized and with max
Given points $x_1, \ldots, x_n$ in the Euclidean space and $K \in \mathbb N$, I'm interested in the following objective.
Partition the points into $K$ clusters $C_1, \ldots, C_K$ so that:
$$\max_{i \...
5
votes
1answer
77 views
A dynamic program to decide whether the solution is in a given range
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
The problem can be ...
3
votes
1answer
141 views
A complexity class between P and FPTAS
The question is about approximation algorithms to NP-hard optimization problems.
For concreteness, let $M$ be a minimization problem with $n$ inputs, where all inputs and outputs are integers in the ...
1
vote
1answer
33 views
Where does each part of the $1 - (1 - 1/k)^k$ approximation for the Maximum Coverage problem come from?
A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most ...
1
vote
0answers
27 views
Routing in ring network topology
I want to find 2-approximation algorithm for finding path of m messages sent from m computers to m different computers in a ring topology with n nodes.
I know about clockwise embedding, which takes ...
2
votes
1answer
44 views
Meaning of "approximation within $n^{1−\epsilon}$"
I am not sure I understand correctly the following assertion (source):
For all $\epsilon > 0$, approximating the chromatic number within $n^{1−\epsilon}$ is NP-hard.
Does this mean that, for any ...
0
votes
1answer
22 views
Maximal edge weight clique of given size
Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. ...
0
votes
1answer
23 views
polynomial time approximation algorithm problem
How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem?
For say we have 2 approximation problems which less than equal 2C*. But when we have a ...
0
votes
0answers
17 views
How to read the optimal makespan
Hello I'm having trouble reading the optimal makespan of job scheduling algorithm. In particular what does it mean for max to have index i here?
0
votes
0answers
13 views
Need Help Solve an NP problem with an Approximation Algorithm
I have an algorithm problem which I do not know how to solve and I think it is NP-complete. Let me try to explain with a general example.
Given $n$ objects, each with $k$ possible properties, ...
0
votes
0answers
101 views
Multivariate piecewise linear interpolation
I am looking for a reference to a solution of the multivariate piecewise linear interpolation. I am not quite sure how to generalize a well-known dynamic programming Segmented Least Squares algorithm.
...
1
vote
0answers
39 views
Exact and approximate agorithms for independent set probem in large graphs
I have a problem which could be stated as follows:
Given an unweighted undirected graph $G=(V, E)$ and positive integer $k \leq |V|$, I need to find a subset of vertices $R \subseteq V$ such that $|R| ...
1
vote
1answer
28 views
Embedding from $L^\infty$ space to $L^2$ space
I have a set $X$ of $n$ points in a $poly(n)$-dimensional $L^\infty$ space. Does there exist a way to map the points into $poly(n)$-dimensional $L^2$ space so that the distances between points in $X$ ...
2
votes
1answer
52 views
What is an O(n)-approximation?
I see the following notations used:
$O(1)$-approximation
$O(n)$-approximation
$\Omega(n)$-approximation
Can someone please explain what they mean?
I know what an approximation is with a normal ...
0
votes
0answers
11 views
Proof of lemma for competitive ratio on subsequence - Strip Packing
In this paper by Azar and Epstein in Section 4 they consider online strip packing of rectangles without rotation in a setting where when a rectangle arrives it has to be lowered monotonically ...
0
votes
0answers
35 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
79 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
23 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
36 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
21 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
36 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
53 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
42 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
34 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
106 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
47 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
16 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
134 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
38 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
23 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
60 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
44 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
27 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
38 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
109 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
35 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
51 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
41 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
34 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
62 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
21 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
44 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
33 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
96 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 ...
