Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
584
questions
1
vote
0
answers
16
views
Approximation Algorithm for Bin packing Variant with Packing Overhead
I recently came up with this bin packing variant and was wondering, if someone has studied it before:
Given: Instance $I$ is a set of tuples $\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$ with $s_{i}, ...
- 11
0
votes
0
answers
15
views
better ways to integer interpolation?
I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate.
Let's refer to "II" as integer interpolation.
...
- 1
0
votes
1
answer
27
views
Optimal randomized algorithm for set cover
This cstheory.SE post gives various randomized approximation algorithms for the set cover problem. Is there a randomized algorithm (which runs in $\mathrm{poly}(n)$ time) for the set cover problem ...
- 1
0
votes
0
answers
9
views
Parametrized threshold for LP Approximation in Vertex Cover Problem
I would like to have a formal description on how parametrizing the threshold in the approximation of vertex cover using LP would impact the approximation factor of the problem.
The linear programming ...
0
votes
0
answers
50
views
Understanding the "Structure Theorem" for the Euclidean Traveling Salesman PTAS
I am trying to understand the "Structure Theorem" in Arora's TSP slides. In particular, I do not understand the image on slide 13-3 (page 68 of the PDF). The high level idea is to show that (...
- 185
0
votes
1
answer
36
views
Weighted interval scheduling on K-identical machines --- approximation factor
This is a follow-up for Weighted interval scheduling with m-machines ---greedy solution with approximation factor.
As suggested by @D.W., I will present the problem more comprehensively.
$\textbf{...
- 11
1
vote
1
answer
55
views
Weighted interval scheduling with m-machines ---greedy solution with approximation factor
Weighted interval scheduling with m-machines
('Weighted interval scheduling with m-machines')
I encountered the problem of weighted interval scheduling on m identical machines (as discussed in the ...
- 11
0
votes
0
answers
29
views
Calculating approximation factor of a TSP algorithm
The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
1
vote
0
answers
29
views
Scheduling jobs with the same release time and different due dates on a single machine
Consider the problem of scheduling jobs with different lengths on a single machine while the jobs have the same release times and different due dates. The goal is to schedule the maximum number of ...
1
vote
0
answers
25
views
What is the name of this extension of the maximum independent set problem?
Problem: we have an undirected graph. Each vertex $v$ has a weight of $w_v$. For each vertex $v$, a nonnegative number $a_v$ is given, and for each edge $e$, a nonnegative number $b_e$ is given. ...
1
vote
0
answers
57
views
What is the name of this matching problem?
We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...
0
votes
0
answers
22
views
Maximum Subset Sum with Pairwise Constraints
(Note: I am posting after reading some possibly related posts because I could not find a fitting solution.)
Given some finite set of nodes $S$, where each node $s_i \in S$ has a value $val(s_i) \in [0,...
- 11
1
vote
2
answers
50
views
Estimating the number of elements shared in two sets using a random sample
Suppose we have two sets $A$ and $B$. The sets share some number of elements between them, but within each set, any item appears at most once. We want to determine how many elements they share in ...
- 837
-1
votes
1
answer
38
views
if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?
if by absurdly there is a 3/2-approximation algorithm for INDIPENDENT SET then does there exist a 3/2-approximation algorithm for VERTEX COVER?
the implication should be true because independent is ...
1
vote
1
answer
49
views
Hardness of the k-center problem with relaxed triangle inequality
Consider the $k$-center problem where we are given an undirected, complete graph $G=(V, E)$, with a distance $d(u, v) \geq 0$ for each pair $u, v \in V$. Furthermore, we assume that the triangle ...
1
vote
1
answer
92
views
First-Fit-Decreasing algorithm packs items of size at most 1 into bins of capacity 2
Consider the bin packing problem where we are given item sizes $a_1,\dots, a_n \in (0, 1)$, and all bins have capacity 2. The task is to pack the items in as few bins as possible, such that the total ...
2
votes
1
answer
119
views
Budgeted Independent Vertex Cover
Suppose that we are given a graph $G = (V,E)$ and a number $n$. The problem is to find an independent set $I$ with $|I| = n$, such that number of vertices covered by $I$ is maximized (that is, the ...
- 131
4
votes
0
answers
74
views
Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph
I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible.
The problem is quite simple:
Given $G = (V, E)$ an undirected graph, ...
- 41
1
vote
1
answer
70
views
How to prove this simple randomized algorithm is 2-approximate for MAS?
The Maximum Acyclic Subgraph (MAS) problem is:
Given a directed graph $G = (V, E)$, find
the largest subset of edges which are acyclic.
In this paper the authors state the following algorithm:
A ...
- 163
1
vote
0
answers
41
views
Can there be a 1.1 approximation algorithm for the load balancing problem?
I know this is a very specific question, but: Let's assume that someone designed a 1.1 approximation algorithm for the load balancing problem involving exactly 2 machines. After running the algorithm ...
- 43
3
votes
1
answer
134
views
Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem
The following problem statement is given:
Let $S = \{s_1, s_2, \cdots, s_n\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s_i$ for every $i$ between $1$ and $n$. ...
- 43
0
votes
0
answers
41
views
Hardness of the bin packing problem
I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that
$$
1 > a_1 \geq a_2 \geq \dots \geq a_n > 0
$$
The ...
1
vote
1
answer
62
views
Decision version of optimization problems with polynomial-time approximation algorithms
Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$.
Therefore, we can define a class ...
- 5,720
1
vote
1
answer
132
views
Chistofides' algorithm for the traveling salesman problem with relaxed triangle inequality
It is known that Christofides’ algorithm returns a 3/2-approximation for the traveling salesman problem given a complete graph $G$ such that distances obey the triangle inequality. Suppose that we ...
1
vote
0
answers
31
views
How to show that my problem cannot be approximated within a certain factor unless P=NP?
Before I introduce my problem I need to define a couple of things. Suppose we have two sets $S_1=\{1,2,3\}$ and $S_2=\{2,3,4\}$. A compression tree for $S_1$ and $S_2$ is
...
0
votes
1
answer
48
views
Which combinatorial problem is reminiscent to mine?
I am trying to understand which combinatorial problem best fits the one I have. I am mostly asking from the perspective of being pointed towards relevant literature. I will explain the problem with an ...
- 321
2
votes
0
answers
84
views
Finding a maximum induced DAG in a digraph
I have a digraph D on n vertices formed in the following manner:
I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more ...
- 71
0
votes
0
answers
109
views
Does there exist an FPTAS for bin packing problem?
We know that there does not exist an FPTAS for the bin packing problem because it is a strongly NP-HARD problem, as the 3-partitioning problem which is strongly np-hard, can be reduced to the bin ...
0
votes
3
answers
183
views
Details of sqrt.c library source code
Have seen library code for finding square-root, using the Newton Raphson method.
It uses a table of 256 entries, whose significance is unclear, as the initial guess should be dependent on the quantity ...
- 187
1
vote
1
answer
96
views
Can we prove the greedy algorithm archives 1.5-approximation for the Minimal Dominating Set Problem?
The following approximation algorithm for the Minimal Dominating Set Problem is said by a fellow student to be a 1.5-approximation:
Start with empty set $S$
As long as not all vertices are covered:
...
- 13
2
votes
0
answers
45
views
Designing Shortest Route
Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
- 63
0
votes
0
answers
17
views
Can a PTAS be called one if it is parameterized by one of the problem inputs (in addition to ε)?
I.e. is it right to say "a PTAS parameterized by sth"?
Is it unusual, and is it correct?
- 1
0
votes
1
answer
45
views
fault-tolerant K-median problem on an undirected graph
We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$:
We are given a set of facilities $F\subseteq V$ and a set of demands (...
- 15
1
vote
1
answer
65
views
Bin packing with more than one parameter
Usually, in bin-packing, we have objects of sizes $a_1,...a_n$, and each bin has size 1, We need to minimize the number of bins, and for this, there are best fit/first-fit approximation algorithms.
...
- 63
0
votes
1
answer
59
views
Geometric Set Cover in one dimension
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem.
The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
- 63
1
vote
1
answer
162
views
Prove the expected size of the independence set got by a random algorithm is at least 1/d of the maximum size
I am doing an exercise related to maximizing Independent Set, I have $G = (V = \{v_1, . . . , v_n\}, E)$ as an undirected graph. This graph as $n!$ possible orderings for the vertices $V$.
If we pick ...
- 25
0
votes
1
answer
105
views
To write an IP and relax it to LP for finding a multi-set in a graph
I am new to Linear Programming and Approximation algorithms. and I am trying to do this exercise for writing an IP and relax it to LP. What I am given:
A digraph ...
- 25
1
vote
0
answers
24
views
tight lower bounds of parallel machine scheduling with gang scheduling constraint
I am interested in tight bounds for the Parallel Machine scheduling problem with a gang scheduling constraint.
In the notation of Graham, Lawler, Lenstra and Rinnooy Kan, this might be called $Pm|\rm{...
- 17.7k
-1
votes
1
answer
435
views
How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover
The problem I am trying to solve is that there is an underlying undirected graph G = (V, E) with weights on the vertices, where the weight on vertex ...
- 25
0
votes
0
answers
55
views
Bin Packing tight analysis lower bound?
I am having a problem understanding the following:
This is the background of the lemma:
To prove the lower bounds, we use the classical lower bound construction from [5, 9]. We
have an input instance ...
- 123
0
votes
0
answers
44
views
The solution of a nonlinear equation and eigenvalues
I have a non-zero vector $x = [x_1,\cdots,x_N]$, $0 \le x_i \ll 1$ and a symmetric matrix $M$ with eigenvalues $\Lambda_1 > \Lambda_2 \ge \dots \ge \Lambda_N$ satifying $$ x_i = \frac{\lambda\sum_{...
- 101
0
votes
0
answers
93
views
How to prove the performance ratio of the approximation algorithm of maximum clique is unbounded
Consider the following approximation algorithm for the problem of finding a maximum clique in a given graph $G$. Repeat the following step until the resulting graph is a clique. Delete from $G$ a ...
- 1
0
votes
0
answers
56
views
asymptotic approximation ratio vs absolute approximation ratio?
I am trying to learn about approximation algorithms. In some research papers, it is mentioned about the absolute approximation ratio. what does the absolute approximation ratio mean? is it different ...
- 123
0
votes
1
answer
82
views
MAX-SAT approximation factor
I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm
MAX-3SAT:
set every variable with a random value ($0$ or $1$ each ...
- 3
0
votes
0
answers
44
views
Approximation Class that Decides
Suppose we have a minimization ILP. Denote its value by $OPT$.
Let $PER$ be the solution to its LP relaxation.
Given a real number $t$, we would like to decide whether $OPT \leq (1+t) \cdot PER$, in ...
- 127
0
votes
1
answer
457
views
Traveling salesman problem on an incomplete graph
In the standard framing of the traveling salesman problem, we're given a complete graph, meaning every pair of vertices has an edge in between them. And this might be close to accurate when the ...
- 305
1
vote
0
answers
15
views
Algorithm for minimizing the number of resources simultaneously open while iterating through a series of tasks
I have a problem where I'm iterating through a series of tasks and each task requires that a specific file is loaded into memory. The files are not allowed to be unloaded until all of the tasks that ...
- 121
2
votes
0
answers
51
views
State of the art implementations of minimum-cost multicommodity flow approximation algorithms
I'm looking for implementations of approximation algorithms (or algorithms that would be meaningful to implement for use in practice) for the minimum-cost multicommodity flow problem as defined in e.g....
- 165
3
votes
0
answers
88
views
Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$ [closed]
Given sorted $0\leq x_1 \leq x_2 \leq ... \leq x_n$ and $y_1 \geq y_2 \geq ... \geq y_n \geq 0$ non negative integers accessible through oracles, with the additional constraints $x_{i+1}-x_i \leq 1$ ...
- 593
1
vote
1
answer
25
views
Efficiently covering a finite set of points in $\mathbb{Z}^3$ by fixed size, axis-aligned cubes?
In my problem of interest I have an arbitrary, finite set $S \subset \mathbb{Z}^3$. And I would like to cover $S$ with a set $C \subset \{T | T \subset \mathbb{Z}^3 \textrm{ is an axis-aligned cube of ...
- 33