Questions tagged [approximation]
Questions about algorithms that solve problems up to some bounded error.
459
questions
1
vote
0answers
108 views
Minimum Degree Spanning Tree Without Restricting Vertices Searched [closed]
I am currently self studying approximation algorithms from The Design of Approximation Algorithms (Williamson and Schmoys; page 50 here), specifically the minimum-degree spanning trees (MDST) problem. ...
2
votes
1answer
47 views
Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time
I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. ...
0
votes
0answers
39 views
Most popular path in weighted cylic directed graph
Context
I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = ...
1
vote
1answer
28 views
Approximate max weight path in directed graph
Context
This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights ...
2
votes
2answers
110 views
Approximation of Set Cover
I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better ...
2
votes
2answers
40 views
Prerequisites for studying parametrized complexity
Which areas of CS/Math should one have mastered before diving into parametrized complexity?
0
votes
6answers
138 views
What algorithm do computers use to compute the square root of a number?
What algorithm do computers use to compute the square root of a number ?
EDIT
It seems there is a similar question here:
Finding square root without division and initial guess
But I like the answers ...
1
vote
1answer
22 views
Find The “Best” Permutation of Inputs to Maximize Sum of Functions (or approximate “best”)
The Problem (in words)
I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the ...
0
votes
0answers
17 views
Best algorithm / method to determine path length from noisy GPS points
i am analyzing a series of GPS points (with time stamps) which are noisy meaning have an accuracy of about 15 meter radius (sometime even more), and i need to extrapolate the distance the vehicle has ...
-2
votes
1answer
62 views
Greedy algorithm for problem asking for solution of size *at most* $k$
Given an integer $k$ and a complete weighted bipartite graph with sides $A,B$ in which the weight of the edge $(i,j)$ is $c_{ij} \geq 0$, we want to find a set $S$ of at most $k$ edges that maximizes $...
2
votes
1answer
38 views
2-Approximation algorithm for for messages across a cyclic network
Question
There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) ...
1
vote
0answers
16 views
Additive approximation to bin packing
The bin packing problem is an NP-hard optimization problem that has many constant-factor approximation algorithms. I am looking for an additive approximation. I.e., given a set $I$ of items and bin ...
0
votes
1answer
29 views
Approximating longest path on graphs with average degree n/2
I have a graph with average degree $n/2$. How I can find an approximation algorithm for the longest path problem with factor $1/4$?
0
votes
1answer
20 views
Approximation algorithms for an instance of the Monotone circuit satisfiability
I have the following problem. Given a below boolean formula (of the type explained below) containing $n$ literals and two parameter $k$ and $l$, come up with a satisfying assignment of literals such ...
0
votes
0answers
41 views
Minimum Dominating Set
Consider a graph $G$ with minimum degree $d$, we know through sets cover, it's possible to find the one dominating set $S$ that covers $G$ such that $$S\leq O(\log n)\frac{n}{d}
$$ with high ...
1
vote
1answer
21 views
linear time nash equilibirum aproximations for two player zero sum games
I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. ...
1
vote
1answer
34 views
Regula falsi with error in x-axis
I want the regula falsi to get x +- .0001 so that f(x) = 0. But all the implemetations I see get x so that f(x) +- .0001 = 0 which doesn't make much sense. (f(x) = x^3).
How do I stop the regula ...
2
votes
1answer
32 views
Why are $L$-reductions defined the way they are?
I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the ...
2
votes
1answer
48 views
Approximation concerning Asymmetric TSP, Symmetric TSP, and Metric TSP
I always considered Symmetric TSP to be inapproximable in general, and thus by extension Asymmetric TSP as well. Once you add the condition of the triangle inequality however, you obtain Metric TSP (...
3
votes
0answers
47 views
Total weight of all spanning trees
Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
0
votes
1answer
55 views
prove: max (w(Eļ ), w(Eļ)) is a 1/2 approximation to the value OPT
Hey I would like to find a answer for b. for a look to the picture that is my answer for it. But I dont habe any Idea how i can solve this. Thank you guys. (I had to translate it to english maybe it ...
3
votes
1answer
45 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
...
-1
votes
1answer
61 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, ...
1
vote
0answers
69 views
Greedy Probabilistic Algorithm for $Exact$ $Three$ $Cover$
I have a probabilistic greedy algorithm for Exact Three Cover. I doubt it'll work on all inputs in polytime. Because the algorithm does not run $2^n$ time. I will assume that it works for some but not ...
0
votes
0answers
13 views
graph augmentation problem for Regional-based connectivity
Region-based connectivity:
Given a graph $G(V,E)$, $\lbrace R_1,..., R_{k}\rbrace$ is the set of all possible regions (A subgraph with diameter $d$ or a subgraph centered at a node with radius $r$) ...
2
votes
0answers
48 views
Complexity of approximating a function value using queries
I am looking for information on problems of the following kind.
There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
5
votes
1answer
75 views
Maximize area of light with 4 light sources on a diagram of a room
Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized.
Here is a simple ...
1
vote
1answer
43 views
TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$
Input: complete, undirected graph $G=(V,E)$ and cost function $c$
Assume for all nodes $x,y,z \in V$: $c(x,z)\le c(x,y) + 100\cdot c(y,z)$
Find a 200-approximation polynomial time algorithm for the ...
0
votes
2answers
61 views
Coloring graph with constraints on assortativity
I have come across the following problem and I would love for your thoughts on an optimal solution or approximate calculations worth trying.
The formulation of the problem in the form of graph theory:
...
1
vote
1answer
39 views
Max independent set in planar graphs PTAS proof
I've been searching a few hours for a proof to Max independent set in planar graphs beeing in PTAS but I couldn't find anything, I'm searching for one without any reductions and I wonder if anyone ...
2
votes
1answer
30 views
Uncapacitated facility location problem using local search
I'm studying about UFLP using the book The Design of Approximation Algorithms Ch 9 starting page 233 (there is an electronic free edition), I ran into some unclear steps in the book and need some help ...
1
vote
1answer
116 views
Approximation algorithm question, clustering on n points
So the algorithm I thought of, is to iterate through the n points, centering a ball at each point, and keeping track of the point where we centered that encapsulated the most points. Then remove the ...
0
votes
0answers
21 views
Applying Polynomial Time Approximation Scheme (PTAS) on an Algorithm
I am trying to apply PTAS on an algorithm. I think that we apply PTAS on the running time equation of the algorithm. We use the term (1-Ļµ) and (1+ Ļµ) in the running time of the algorithm but I donāt ...
0
votes
0answers
20 views
Set Cover: Understanding the algorithm with an example
I am trying to follow the following link:
Solution for an example
They have provided solution for an example using the greedy algorithm. I have got following questions:
(1)Why start with Z, cost is 7, ...
5
votes
5answers
306 views
fast and stable x * tanh(log1pexp(x)) computation
$$f(x) = x \tanh(\log(1 + e^x))$$
The function (mish activation) can be easily implemented using a stable log1pexp without any significant loss of precision. Unfortunately, this is computationally ...
1
vote
1answer
40 views
Variant of greedy algorithm for vertex cover
Does the following approximation algorithm for vertex cover also have an approximation ratio of 2? Why? Why not?
Input: $G = (V,E)$
Set $C \gets \emptyset$ and $E' \gets E$.
while $E' \neq \emptyset$...
2
votes
1answer
58 views
Greedy algorithm for job scheduling
Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime.
How to prove that this algorithm has an approximation ratio of ...
1
vote
0answers
36 views
Longest processing time rule on unrelated machines
I am trying to solve the job secheduling problem using the Longest processing time rule, that is: We seek to minimize the makespan by first sorting the jobs in decreasing order of processing time, ...
3
votes
1answer
87 views
Maximum coverage 1/2-approximation algorithm: why does the central lemma hold?
I am looking for an approximation algorithm for the Maximum Coverage problem and a proof of its approximation ratio. As approximation algorithm I use the greedy algorithm which chooses the set that ...
1
vote
1answer
314 views
Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > $0
Suppose you have a system that consists of $m$ slow machines and $k$ fast machines. The fast machines can perform twice as much work per unit time as the slow machines. Now you are given a set of n ...
0
votes
0answers
19 views
Solving the multiple-choice knapsack problem for large input
I need to solve the multiple-choice knapsack problem for a very large input size ($\approx 10,000,000$).
What is best way to practically do this? I've seen some papers describing FPTAS (=Fully ...
1
vote
0answers
34 views
Heuristic algorithm for the minimum weighted s-t cut with linear running time
To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $O(n^{2}\sqrt{m})$ time complexity. I'm interested in solving ...
0
votes
1answer
25 views
Piecewise linear approximation for set of points
If we have a set of points $A$ and a known algorithm $Bestfit(A)$ to find
the best-fit straight line-segment through $A$, what would be a good algorithm to construct piece-wise linear segments (with ...
0
votes
2answers
76 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{...
0
votes
0answers
33 views
Approximation Set Covering Problem
I am studying approximation Set Covering problem, from "Introduction to Algorithms by Thomas H. Cormen" book. What I cannot understand is why they use harmonic numbers to the proof? What harmonic ...
1
vote
1answer
26 views
3-Approximation for General position subset
I am currently studying for an exam and stumbled upon the following task:
Given the following problem:
Input A set of points $P \subseteq \mathcal{Q}^2$ and $k \in \mathbb{N}$
Question Find the ...
1
vote
0answers
51 views
Minimum-cut with balanced and limited number of nodes in each partition: Does this have an efficient solution or even a name?
I'd like to remove the minimum number of edges from an undirected unweighted graph to partition the nodes into an arbitrary number of connected components $S_1$, $S_2$,$S_3$,... $S_k$ while maximizing ...
2
votes
0answers
108 views
PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks
Consider the following problem:
We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...
0
votes
1answer
17 views
Compendium of approximation ratios, with narrower scope and more up to date than the NP-compendium?
I usually check the NP-compendium from Pierluigi Crescenzi, and Viggo Kann when I want to know the APX status and approximability results of a problem.
However, I understand that maintaining it is a ...
0
votes
2answers
46 views
Calculating match % and ranking according to that
I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown ...
