# Questions tagged [approximation]

Questions about algorithms that solve problems up to some bounded error.

447 questions
Filter by
Sorted by
Tagged with
25 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 ...
29 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 ...
38 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 (...
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 ...
49 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 ...
32 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 ...
57 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, ...
68 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 ...
12 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$) ...
45 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 ...
72 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 ...
42 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 ...
55 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: ...
32 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 ...
25 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 ...
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 ...
17 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 ...
19 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, ...
277 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 ...
34 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$...
43 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 ...
34 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, ...
63 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 ...
150 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 ...
18 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 ...
33 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 ...
24 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 ...
57 views

34 views

### Estimating number of points in 1D space

There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for ...
60 views

### Doubt on integrality gap and LP relaxation

I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-...
218 views

122 views

### Minimum edge weight k-exact cover with triangle inequality

Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$ satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$. Suppose $k \in \mathbb{N}$ (in ...
78 views

### Approximation algorithms for indefinite quadratic form maximization with linear constraints

Consider the following program: \begin{align} \max_x ~& x^TQx \\ \mbox{s.t.} ~& Ax \geq b \end{align} where $Q$ is a symmetric (possibly indefinite) matrix and the inequality is element-wise ...
### Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem
The unweighted maximum coverage problem is defined as follows: Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$. Objective: find a subset $S' \subseteq S$ such ...