Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
550
questions
1
vote
1
answer
52
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
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 ...
- 37
1
vote
1
answer
30
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 ...
- 369
-2
votes
1
answer
47
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
27
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,871
0
votes
1
answer
63
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 ...
- 369
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 ...
- 201
1
vote
1
answer
43
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
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
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
18
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 ...
- 11
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-...
- 201
1
vote
1
answer
70
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
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
1
vote
1
answer
38
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 ...
- 123
1
vote
1
answer
39
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
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 ...
- 1
0
votes
0
answers
66
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 ...
- 81
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 ...
- 158
0
votes
1
answer
38
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 ...
1
vote
1
answer
48
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-...
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 ...
1
vote
0
answers
86
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 ...
- 111
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.
...
- 5,704
3
votes
1
answer
58
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 ...
- 133
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 \...
- 196
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,704
3
votes
1
answer
146
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 ...
- 5,704
1
vote
1
answer
40
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
0
answers
33
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 ...
- 11
2
votes
1
answer
58
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 ...
- 291
0
votes
1
answer
30
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. ...
- 398
0
votes
1
answer
41
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
0
answers
19
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?
- 23
0
votes
0
answers
17
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, ...
- 101
0
votes
0
answers
108
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
1
vote
0
answers
41
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| ...
- 111
1
vote
1
answer
30
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$ ...
- 196
2
votes
1
answer
78
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 ...
- 298
0
votes
0
answers
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
1
answer
115
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 ...
- 314
0
votes
0
answers
25
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{...
- 137
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:
...
- 103
1
vote
1
answer
26
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) ...
- 5,704