Questions tagged [approximation]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 (...
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
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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, ...
1
vote
0answers
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 ...
0
votes
0answers
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$) ...
2
votes
0answers
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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: ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
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
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 ...
0
votes
0answers
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, ...
5
votes
5answers
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 ...
1
vote
1answer
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$...
2
votes
1answer
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 ...
1
vote
0answers
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, ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
57 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
24 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
46 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
95 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
0answers
33 views

Scheduling jobs on a single machine - minimising the weighted sum of completion times

Consider the following problem: there are $n$ jobs $\{1,...,n\}$, each has a processing time, $p_i$, a weight $w_i$, and an arriving time $r_i$. The goal is to minimise the weighted sum of completion ...
0
votes
0answers
36 views

Graham 1966 Minimum makespan scheduling

I am trying to understand how Graham's 1966 makespan algorithm results in 2-approximation. I have searched in google and I have found files, and videos on youtube about makespan scheduling, but again ...
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
44 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 ...
0
votes
0answers
52 views

A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
8
votes
0answers
123 views

Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
2
votes
0answers
23 views

FPTAS algorithm to find flow at each link for multi commodity flow problem?

Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
1
vote
1answer
578 views

Derandomization of vertex cover algorithm

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set: Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$. Add to ...
3
votes
1answer
87 views

Integrality gap and LP-rounding

I have a doubt about integrality gap. If I know that there is no integrality gap for a given problem, i.e.: $$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$ ...
3
votes
0answers
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 ...
0
votes
0answers
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-...
9
votes
1answer
218 views

2D interval scheduling problem

Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
9
votes
2answers
289 views

Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you ...
1
vote
0answers
24 views

ln(n) + 1 Approximation for Set Cover constructions

Set Cover Problem: Given a set $X$ and a collection of subsets $S_1, S_2, \ldots S_m \subseteq S$, we want to find the smallest cardinality of a set of $k$ elements $\{i_1, \ldots i_k \}$ such that $\...
5
votes
1answer
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 ...
4
votes
0answers
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 ...
0
votes
0answers
38 views

A heuristic for finding an edge cycle cover

I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph. In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
1
vote
0answers
79 views

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 ...

1
2 3 4 5
9