Questions tagged [approximation-algorithms]

Questions about approximation algorithms.

Filter by
Sorted by
Tagged with
4 votes
0 answers

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 ...
Yaroslav Bulatov's user avatar
27 votes
3 answers

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 ...
Yaroslav Bulatov's user avatar
11 votes
2 answers

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 ...
user834's user avatar
  • 2,786
22 votes
2 answers

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

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 ...
Shiva Kintali's user avatar
11 votes
2 answers

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 ...
Suresh Venkat's user avatar
15 votes
1 answer

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 ...
user834's user avatar
  • 2,786
11 votes
4 answers

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)$ ...
Aaron Roth's user avatar
  • 9,850
5 votes
1 answer

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 ...
miao's user avatar
  • 161
8 votes
2 answers

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 ...
Yaroslav Bulatov's user avatar
11 votes
2 answers

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 ...
miao's user avatar
  • 161
49 votes
8 answers

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 ...
Kaveh's user avatar
  • 21.5k
29 votes
4 answers

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$ ...
Jukka Suomela's user avatar

7 8 9 10