Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
549
questions
0
votes
2
answers
126
views
Numerical Approximation in Java
I am trying to solve an equation which I believe cannot be done analytically, but can use a numerical approximation to get a result. The equation is:
$$\frac{2*\sqrt{\pi}*h*s*e^{m^{2}/(2*s^2)}}{\sqrt{...
CommunityBot
- 1
1
vote
1
answer
146
views
Job scheduling approximation
In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf
Lemma 5 is given as:
The approximation factor of the modified greedy [scheduling] algorithm is 4/3....
CommunityBot
- 1
5
votes
1
answer
363
views
Minimal Steiner Tree in unweighted directed graph
I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
CommunityBot
- 1
1
vote
1
answer
64
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 $...
CommunityBot
- 1
0
votes
1
answer
183
views
set cover to edge cover
I want to find set cover of this problem.
I have sets, each of cardinality 3. I want to find set cover.
This is what I am doing.
Treat each set as an edge, which is incident on each of its element.
I ...
CommunityBot
- 1
1
vote
0
answers
63
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:
...
- 23.8k
0
votes
1
answer
629
views
Proving there is no polynomial algorithm for independent set
I need some guidance in an assignment I'm doing.
I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the ...
3
votes
4
answers
898
views
Better results for minimum vertex cover algorithms
Currently I'm using the well-known ratio-2 algorithm which is nice and fast, but I'm looking for an intuitive way to improve my results.
All the articles I read so far were way too complicated for me,...
0
votes
1
answer
65
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 ...
- 34.7k
0
votes
0
answers
20
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 ...
- 51
1
vote
1
answer
39
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 ...
- 248
-2
votes
1
answer
48
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 ...
D.W.♦
- 143k
1
vote
1
answer
35
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 ...
- 34.7k
1
vote
1
answer
44
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 ...
CommunityBot
- 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
28
views
Max matching algorithm lemma approximation algorithm
We have this algorithm which is supposed to find max matchings.
...
- 4,093
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,871
3
votes
1
answer
2k
views
Run Christofides algorithm by hand with wrong result
I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
Calculate minimum spanning tree T:
Calculate the set of vertices O with odd degree in T....
- 34.7k
0
votes
1
answer
41
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?
CommunityBot
- 1
0
votes
1
answer
17
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 ...
- 23.8k
3
votes
1
answer
153
views
Approximation factor preserving reduction
The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365:
Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving
...
CommunityBot
- 1
6
votes
1
answer
287
views
Find maximal subgraph containing only nodes of degree 2 and 3 [closed]
I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
CommunityBot
- 1
1
vote
0
answers
64
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
3
votes
1
answer
311
views
smaller size approximation to minimum vertex cover
Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum?
Usual algorithms seems to aim to find an approximation such that ...
CommunityBot
- 1
0
votes
1
answer
83
views
On FPTAS and many one parsimonious reductions
We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction.
If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have?
If $\Pi_2$ has an ...
CommunityBot
- 1
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
19
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
22
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
38
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-...
- 1,475
3
votes
1
answer
59
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 ...
- 410
1
vote
1
answer
72
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, ...
- 270k
1
vote
0
answers
23
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
0
votes
2
answers
40
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:
...
- 4,340
1
vote
1
answer
39
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 ...
- 457
1
vote
1
answer
41
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}$, ...
- 34.7k
0
votes
0
answers
11
views
How to evaulate the upper-bound for a multiobjective optimazation problem?
Given a product set $P$, where each product $p_i \in P$ has a cost $p_i.\!c$ and a value $p_i.\!v$. Therefore, $\forall p_i \in P$, $p_i.\!c > 0$ and $p_i.\!v > 0$. The cost-efficiency of a ...
- 270k
0
votes
0
answers
67
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
3
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 ...
- 4,340
1
vote
0
answers
22
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
29
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 ...
- 270k
0
votes
1
answer
39
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 ...
- 364
1
vote
1
answer
50
views
Finding 2 paths between 2 source-target pairs
Given an undirected graph $G=(V,E)$ and 2 sources $s_1,s_2$ and 2 targets $t_1,t_2$, I am looking to find paths $P_1$ and $P_2$, where $P_i$ is a path from $s_i$ to $t_i$ and $P_1$ and $P_2$ are edge-...
- 3,976
1
vote
0
answers
22
views
Proof that there isn't a $c$-additive approximation to Partition Problem
Define
Partition to consist of all tuples $x_1,\ldots,x_n$ which can be divided to two groups in which the sums of the two groups are equal.
Is there a proof that there isn't an additive approximation ...
- 270k
2
votes
2
answers
100
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.
...
- 3,976
5
votes
1
answer
111
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 ...
- 5,726
1
vote
0
answers
94
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 ...
- 270k
-1
votes
1
answer
72
views
acyclic and disjoint union
I would like to find a prove of (a) so that the two E are acyclic and disjoint union and I dont unterstand b Could someone shed light on this problem, preferably spiced with some intuition?
Thanks, ...
CommunityBot
- 1
1
vote
1
answer
147
views
Why does this algorithm not have an exponential complexity?
In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif
https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf
The authors present a PTAS algorithm that can ...
- 126
4
votes
0
answers
39
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 \...
- 227
3
votes
1
answer
148
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 ...
- 270k