# Questions tagged [approximation]

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

549 questions
Filter by
Sorted by
Tagged with
5k views

### Decision problems vs "real" problems that aren't yes-or-no

I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
39k views

### Algorithm to distribute items "evenly"

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
2k views

### Why are NP-complete problems so different in terms of their approximation?

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory. One thing that I've noticed is that while many problems are NP-complete, when ...
2k views

### Approximating the Kolmogorov complexity

I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (...
512 views

### Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
3k views

### Why there are no approximation algorithms for SAT and other decision problems?

I have an NP-complete decision problem. Given an instance of the problem, I would like to design an algorithm that outputs YES, if the problem is feasible, and, NO, otherwise. (Of course, if the ...
12k views

### PTAS definition vs. FPTAS

From what I read in the ...
306 views

### How can you bound the error of an approximation without knowing the optimal solution?

I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length ...
312 views

### Approximation of minimum bandwidth on binary trees

Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. The decision problem is NP-complete even for ...
17k views

### What does the 2 in a 2-approximation algorithm mean?

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
1k views

### Why are all problems in FPTAS also in FPT?

According to the Wikipedia article on polynomial-time approximation schemes: All problems in FPTAS are fixed-parameter tractable. This result surprises me - these classes seem to be totally ...
4k views

### What is a bicriteria approximation algorithm?

What is a bicriteria approximation algorithm? This keeps coming up in the case of data stream clustering. Is this related to multi-objective optimization? This is where I came across it: cis.upenn....
178 views

### Does #$P$-Completeness imply approximation hardness?

Let $\Pi$ be some counting problem which is known to be #$P$-Complete. Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
1k views

### Average length of s-t (simple) paths in a directed graph

Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating ...
10k views

### Difference between heuristic and approximation algorithm?

i have a problem regarding the following situation. I have two arrays of numbers like this: ...
4k views

### Knapsack Greedy Approximation: Worst Case

I am currently studying approximation algorithms and I have run into an issue with a study problem. The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, ...
326 views

### Hardness of approximating 0-1 integer programs

Given a $0,1$ (binary) integer program of the form:  \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} &...
178 views

654 views

### What is the name of this logistic variant of TSP?

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
3k views

### Why is Savage's Vertex Cover algorithm a 2-approximation?

Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem. Given graph $G$, start at arbitrary node and traverse $G$ depth-first Obtain DFS tree $T$ return $V_C =$...
3k views

### Providing Tight Example in Approximation Algorithm Analysis

Let's say I found a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight. Do I now need to come up with an example of generic size $n$ or does it suffice to ...
114 views

### What is the approximation ratio of this bin-backing algorithm?

Consider the following algorithm for bin packing: Initially, sort the items by their size. Put the largest item in a new bin. Fill the bin with small items in ascending order of size, up to the ...
6k views

### Balanced Weight Distribution in Bins/Buckets

Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which is ...
510 views

### The heaviest induced subgraph problem

I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w_v: V \mapsto R$, and $w_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ ...
156 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$. ...
86 views

328 views

### MAXSAT approximation

We have been studying a 1/2-approximation for MAXSAT which runs in expected polynomial time, by randomly assigning True/False to each variable and repeating until we reach an assignment with at least ...