Questions tagged [approximation-algorithms]
Questions about approximation algorithms.
513
questions
4
votes
0
answers
231
views
Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?
I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
- 4,681
27
votes
3
answers
988
views
When is relaxed counting hard?
Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
- 4,681
11
votes
2
answers
3k
views
Integer Factoring via Lattice Reduction?
I found a paper titled "Factoring integers and computing discrete logarithms via diophantine approximation" by C. P. Schnorr from 1993. It looks like a probabilistic method with expected polynomial ...
- 2,786
22
votes
2
answers
1k
views
Polynomial time approximation algorithms for machine scheduling: how many open problems are left?
In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
39
votes
9
answers
4k
views
Optimal greedy algorithms for NP-hard problems
Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
- 10.6k
11
votes
2
answers
548
views
Average distortion embeddings
Consider two metric spaces $(X, d)$ and $(Y, f)$, and an embedding $\mu : X \rightarrow Y$.
Traditional metric space embeddings measure the quality of $\mu$ as the worst-case ratio of original to ...
- 32k
15
votes
1
answer
949
views
Integer relation detection for Subset Sum or NPP?
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
- 2,786
11
votes
4
answers
490
views
Dimensionality reduction with slack?
The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ ...
- 9,850
5
votes
1
answer
445
views
High probable polynomial time algorithm for NP-hard problems?
Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the ...
- 161
8
votes
2
answers
356
views
complexity of fitting models to data
Suppose $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ is some some continuous function
$x_1 \ldots x_n$ is a set of real values, and we'd like to compute
$\text{argmin}_a \sum_i f(a,x_i)$ to ...
- 4,681
11
votes
2
answers
5k
views
Any fast algorithm for minimum cost feedback arc set problem?
In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set.
If each edge is associated with a weight $w$, the minimum cost ...
- 161
49
votes
8
answers
9k
views
The importance of Integrality Gap
I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
- 21.5k
29
votes
4
answers
2k
views
Bounded-cardinality bounded-frequency set cover: hardness of approximation
Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.
Example: the case $k = 4$ ...
- 11.5k