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. ...
• 20.4k
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 ...
• 433
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 ...
• 505
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 (...
• 333
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 ...
• 321
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 ...
• 673
12k views

PTAS definition vs. FPTAS

From what I read in the ...
• 1,405
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 ...
• 889
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?
• 131
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 ...
• 8,937
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....
• 289
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$)?
• 2,594
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 ...
• 245
10k views

Difference between heuristic and approximation algorithm?

i have a problem regarding the following situation. I have two arrays of numbers like this: ...
• 337
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

• 364
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 ...
• 22.1k
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 =$...
• 343
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 ...
• 81
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 ...
• 5,726
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 ...
• 211
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$. ...
• 4,093
86 views

• 71k
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 ...
• 344