Questions tagged [approximation]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

maximal independent set on grid-based graph proof of approximation ratio

We have a G = (V, E, w), in form of a grid graph with a single diagonal line in each grid in form of below. Where w is the V weight. We use a greedy algorithm that takes in each step maximum weighted ...
0
votes
1answer
18 views

maximal independent set on grid graph proof

I'm trying to figure out proof of maximum independent set from: this link. (1b part). And I'm bit confused why exactly sum of $w(v)$ is less than or equal to sum of $w(v')$. Shouldn't it be other way ...
1
vote
1answer
47 views

k-polynomial time approximation algorithm for set cover (k = max size of subsets)

Problem Definition: Given a universe set $U = \{1, 2, \dots, n\}$ and a collection of $m$ subsets $S_1, S_2, \dots S_m \subseteq U$, find the minimum collection of subsets that cover $U$. I am ...
1
vote
1answer
28 views

Reduction from TSP to ATSP does not imply constant factor approximation algorithm

As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am ...
1
vote
0answers
42 views

The correct way to calculate the performance of my approximate algorithm

I've got a question about how best to classify the performance of an approximate algorithm. I'm trying to find the 'correct' value of a graph problem instance whose cost function has an objective ...
1
vote
1answer
17 views

Can PTAS $\epsilon$ parameter be dependent on the algorithm input?

Let A be a PTAS algorithm with time complexity $O\left(\frac{1}{\epsilon}\right)$. Let $n$ be the input of the algorithm A. From Wikipedia: The running time of a PTAS is required to be polynomial in $...
0
votes
1answer
25 views

How are matchings a lower bound for an approximate vertex cover?

I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover. They mention that the 2-approximation ratio is a lower bound. How is a maximal matching ...
1
vote
0answers
31 views

Polynomial variable of inapproximability after reduction

I proved the inapproximability of a problem that, given a multigraph $G = (V, E)$ and a set of vertices $U \subseteq V$ tries to maximize a score $f(U)$ whose value depends on the edges of the graph, ...
-1
votes
2answers
19 views

Can you have an approximation that is higher than the optimal for a maximum value and a lower than the optimal for a minimum value?

I was reading this page on approximation ratios and the author says that for a problem looking for a: maximum, an approximation algorithm will give us a value lower than this optimal maximum minimum, ...
1
vote
1answer
21 views

Are disjoint edges the same as matchings?

I am reading Chapter 9 Approximation Algorithms of Dasgupts et al.'s Algorithm book for vertex cover approximation and they bring up the concept of matchings. To support this, I am also watching ...
1
vote
1answer
95 views

Where does 1.3606 approximation ratio come from for vertex cover approximation?

I was watching a coursera video on Approximation algorithms and I understood the 2-approximation algorithm. Later, the professor asks if we can do any better. The lecturer went on to say that ...
2
votes
2answers
79 views

Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part

Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
2
votes
1answer
33 views

k-center problem: proof for Gon algorithm gives a 2-approximation

The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following ...
-1
votes
1answer
57 views

Clique is NP hard to approximate up to $n^{a}$ for some $a \in (0,1)$

Given that $\mathsf{NP}=\mathsf{PCP}_{[\frac{1}{n},1]}\left(O\left(\log n\right),\left(O(\log n\right)\right)$, show that it is NP-hard to approximate clique up to factor of $n^a$ for some $a \in (0,1)...
1
vote
1answer
25 views

Online approximation algorithm for median?

Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c_1,c_2,c_3,\dots$? The scenario is: I have a ...
1
vote
0answers
30 views

Cover a surface with disks of various size

I'm trying to find a cover of a surface using disks of variable sizes. In the image, I want to cover the entire blue surface. The disks can go "out" of the blue surface and into the red part,...
0
votes
0answers
28 views

Is there an approximation algorithm for the three-person stable roommates problem?

While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", ...
1
vote
0answers
135 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
49 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
42 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
41 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
123 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
43 views

Prerequisites for studying parametrized complexity

Which areas of CS/Math should one have mastered before diving into parametrized complexity?
0
votes
6answers
186 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
34 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
18 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
42 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
48 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$?
1
vote
1answer
29 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
44 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
43 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
61 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
66 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
53 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
62 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
70 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 ...
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
78 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
44 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
62 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
45 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
34 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
118 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
21 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
321 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
2 3 4 5
10