# Questions tagged [approximation]

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

577 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

### Inapproximability of graph problems on a restricted setting

I am considering the following problem $\mathcal{P}$. $\mathcal{P}$: Given an undirected graph $G$, and an integer $k$, find a set of vertices $S \subseteq V(G)$, with $|S| = k$, such that the number ...
154 views

### Is there an FPTAS for 3-way number partitioning?

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
1 vote
59 views

### Hardness of multiplicative vs. additive approximation

Chlebik and Chlebikova prove that the problem "maximum 3-dimensional matching" is NP-hard to approximate within a multiplicative factor of $95/94$. This means that, unless $P=NP$, there is ...
• 5,894
36 views

### What is a term for a problem that is hard to approximate within a factor $c$?

Let $f$ be a maximization problem. If there is a reduction from SAT to the following problem: "given an integer $c$, decide if there is an $x$ for which $f(x)\geq c$", then $f$ is NP-hard. ...
• 5,894
58 views

### An approximation variant of the halting problem

It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable. I have just thought of a variant approximation-...
• 11.4k
62 views

### Universal approximation bounds of the form $\|f(x)-\hat{f}(x;w)\|\leq \varepsilon \|f(x)\|$

It is known that for every $\varepsilon>0$ there is an appropriate neural network architecture, such that one can approximate any continuous function $f:[0,1]^n\to[0,1]^m$ by the neural network ...
164 views

### $\epsilon$-approximation Sub-linear time monotonicity testing

I have the following exercise I have been staring at for several hours to no avail. Question: Testing the monotonicity of a function - the case of bits: Given a function $f: [n] \rightarrow \{0,1\}$ ...
• 193
88 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 ...
• 128
1 vote
73 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
46 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 ...
• 111
1 vote
60 views

• 364
255 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 ...
• 23
95 views

• 111
1 vote
253 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 ...
• 111
270 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 ...
• 41
62 views

### Prerequisites for studying parametrized complexity

Which areas of CS/Math should one have mastered before diving into parametrized complexity?
• 23
1k 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 ...
• 119
1 vote
196 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 ...
• 113
21 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 ...
• 101
202 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$) ...
• 2,923
1 vote
31 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 ...
• 5,894
75 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
58 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 ...
• 111
88 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
26 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. ...
• 3,760
1 vote
70 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 ...
79 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 ...
• 393
209 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 (...
• 675
62 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 ...
• 141
181 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 ...
254 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 ...
• 143
76 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
73 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 ...
• 309
50 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,894
86 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 ...
• 53
1 vote
69 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 ...
• 31
72 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: ...
• 115
1 vote