Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
560
questions
0
votes
0
answers
54
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
69
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 ...
- 155
0
votes
0
answers
19
views
How to optimize an approximated matrix multiplication?
Suppose the objective I try to maximize is
$$\max_{X} \|(I - \alpha X)^{-1}XA\|_F$$
where $X$ is the matrix needs to be pinned down, $\alpha$ is a scalar, and $\|\cdot\|_F$ is the Frobenius norm. Note ...
1
vote
1
answer
62
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
42
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 ...
- 43
0
votes
0
answers
15
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
0
answers
9
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 (...
- 1
1
vote
1
answer
56
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.
...
- 43
0
votes
1
answer
45
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 ...
- 43
1
vote
1
answer
95
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
97
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
21
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.5k
-1
votes
1
answer
145
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
49
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 ...
- 113
0
votes
0
answers
43
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
25
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
17
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 ...
- 113
0
votes
1
answer
49
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
41
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 ...
0
votes
1
answer
171
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 ...
- 295
1
vote
0
answers
14
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
35
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
86
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$ ...
- 595
1
vote
1
answer
21
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
1
vote
0
answers
67
views
Estimating column sums of $A_1,\ A_1 A_2,\ A_1A_2A_3,\ \ldots$
Given $n\times n$ dense real valued matrices $A_1,\ldots, A_L$ let $P_i=A_1\ldots A_i$
For each $P_i$ I'm interested in obtaining the sum of all rows, and the sum of all columns.
Naive approach:
...
- 169
1
vote
1
answer
69
views
Reducing euclidean TSP of smaller size to euclidean TSP of bigger size
Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver.
Now, I have an input with $K$ vertices in the 2D plane, where $...
- 11
0
votes
0
answers
22
views
How can I find the largest bipartite graph?
A bipartite graph corresponds to a rectangle of ones in the adjacency matrix of this graph.
Having a sparse graph, I would like to find the largest approximated bipartite graph.
approximated means ...
- 59
1
vote
1
answer
71
views
MAX-SAT 2-Approximation algorithm
I have the two following questions:
I know SAT -> MAX-SAT but how can I show that if MAX-SAT is solved in polynomial time then SAT is solved in polynomial time as well?(I guess using approximation ...
- 37
1
vote
1
answer
256
views
Proving that the greedy algorithm for job scheduling has a 2 - (1/m) approximation ratio
In the scheduling problem, the input is a sequence $T_1,T_2,...,T_n$ which are the times of $n$ jobs to be executed in m identical machines. A schedule is an assignment of the jobs to machines.
The ...
- 391
-2
votes
1
answer
50
views
Approximate x*(a/b)^(c/d) using integer arithmetic only (assembler)
0 < x,a,b,c,d < M are all positive integers (uint64).
also, a<b if that helps.
we have assembler (integer only) operations available (e.g. division only yields integers).
we want to ...
- 1
0
votes
0
answers
16
views
Is Disjoint Edge Weighted Group Steiner Tree problem equivalent to the regular Steiner Tree problem?
Disjoint Group Steiner Tree (DGST) is the following problem:
Instance: a positive edge-weighted graph $G=(V,E,w)$, a collection of $k$ vertex sets (groups) $S_1,\dots,S_k \subseteq V$, such that $S_i \...
1
vote
1
answer
56
views
Max matching algorithm lemma approximation algorithm
We have this algorithm which is supposed to find max matchings.
...
- 37
0
votes
0
answers
36
views
Special case of single vehicle routing
I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
- 2,913
0
votes
1
answer
86
views
approximation ratio of TSP problem where the weights are bounded by an inequality
Consider a variant of the TSP problem where the cost function $c$ is not only symmetric
but also satisfies $c(u, v) ≤ 2c(u, w) + c(w, v)$ for arbitrary vertices $u, v, w ∈ V$ . Give a
polynomial time ...
- 391
0
votes
1
answer
22
views
Is $\frac{opt}{c}(1-\epsilon)$ for some constant c >0 considered a PTAS?
So I am studying PTAS algorithms. For a maximazation problem the difinition says that an algorithm that has value A , is a ptas if :
$A \geq opt(1-\epsilon) \; ,\forall \epsilon > 0$
(and I guess ...
- 211
1
vote
1
answer
51
views
Can we show that #3CNF is in FPTAS
If we have a deterministic algorithm $A$ such that $\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\#3CNF$? How can we show that $\#3CNF \in ...
- 33
1
vote
0
answers
66
views
Does the existence of an $\alpha$-approximation scheme for a problem $f$ imply there exists a fully polynomial (deterministic) approximation scheme?
If you have an $\alpha$-approximation algorithm $A$ for some problem $f \in \#P$, such that (for $0 < \alpha \leq 1$)
$$
\alpha f(x) \leq A(x) \leq \frac{f(x)}{\alpha},
$$
does that automatically ...
- 33
1
vote
0
answers
21
views
Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?
This problems comes from AI, and it looks something like this:
I am supposed to multiply two floating-point matrices A * B. A ...
- 11
1
vote
0
answers
45
views
Algorithm for modified 2D irregular bin packing
So usually bin packing algorithms compute the tightest packed solution. I want to calculate the opposite, in my case the solution with the most space between the packed objects is needed. I tried ...
- 111
0
votes
0
answers
26
views
How to proof This for Maximum Independent Set Problem?
Show that the problem of finding a Maximum Independent Set doesn't have approximation with factor $\Omega(\frac{1}{n^{1-\epsilon}})$ unless P = NP.
1
vote
1
answer
51
views
Why DFS transversal without the duplicates is a valid cycle?
So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get.
Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path.
The well-...
- 211
1
vote
1
answer
93
views
Inapproximability of an optimization problem
Suppose we have an optimization problem $\mathcal{P}$ that we should cover all points with $k$ disjoint rectangles in the plane and we should optimize a distance function over each rectangles . Now, ...
- 1
1
vote
0
answers
27
views
Weighted k-medians problem
Facility location and $k$-medians are closely related problems in CS. We are given a set of facilities (each with a weight), a set of clients to serve where a facility $i$ can serve a client $j$ with ...
- 129
1
vote
1
answer
40
views
Generate degree-bound LFSR to approximate given sequence
Given an output sequence, $S$, we can use the Berlekamp-Massey algorithm to find the shortest LFSR, of order $n \leq |S|$, which exactly generates that sequence. Is it possible to efficiently compute ...
- 148
1
vote
1
answer
47
views
Is there a way to determine the LCS of three based on the LCS-s of all three pairs?
Let $\Sigma$ be an alphabet of some symbols, and let $\mathrm{lcs}$ denote the length of the longest common subsequence of two or more sequences defined on $\Sigma$. For some $A,B,C\in\Sigma^{\star}$, ...
- 111
0
votes
0
answers
94
views
Can this kind of NP-Hard problem be approximated?
Consider this kind of optimization problem:
(1) The problem aims to minimize a value. Let n denote this value.
(2) To determine whether n = 0 is a NP-Complete problem.
It is obvious that this kind of ...
- 69
7
votes
5
answers
2k
views
What is the fastest algorithm to approximate an irrational number with specified precision?
Problem Background:
Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $[0,1]\backslash \{a\}$, denoted as $x$, the black box outputs boolean ...
- 181
1
vote
0
answers
23
views
Best known approximation for P2|tree;pj=1;Mj|Cmax
I am looking for the best known approximation algorithm for the scheduling problem $P2|tree;p_j=1;M_j|C_{max}$, which to my knowledge is at least $\mathbb{NP}$-hard.
A more elaborate description of ...
- 11
1
vote
1
answer
31
views
Radius Local Search Algortihm for Max-Sat problem approximating ratio
Assume that in classical Local Search algorithm for MAX-SAT we could flip no more than $r
\leq n/2$ variables (let's call it $r$-flip) on every iteration. More precise: on every iteration we're ...
- 158
0
votes
1
answer
41
views
Using an optimal number of agents, maximise coverage of an area while minimising distance travelled
I'm a CS Year 2 student working on a team project which requires a solution to the following problem:
Given a starting position on the edge of an irregular shape (example above) and a maximum number ...
