Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

more tags

Active Hot Week Month

-1

votes

1

answer

51

views

the shorstest cycle containing two given points

cc.complexity-theory approximation-algorithms approximation-hardness planar-graphs

answered 2 days ago David Eppstein 47.6k

4

votes

1

answer

946

views

Is an algorithm with an approximation factor of 4000 useful?

approximation-algorithms approximation

modified Jan 12 at 7:37 Hermann Gruber 4,299

5

votes

0

answers

58

views

Relaxed minimum dominating set

approximation-algorithms randomized-algorithms integer-programming

modified Dec 12 '19 at 10:38 AmeerJ 577

6

votes

1

answer

215

views

What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?

ds.algorithms graph-algorithms approximation-algorithms exp-time-algorithms

modified Dec 6 '19 at 1:25 R B 9,035

0

votes

0

answers

55

views

What is the run-time of LP?

approximation-algorithms time-complexity linear-programming

modified Nov 11 '19 at 1:16 gradstudent 1,353

0

votes

0

answers

39

views

Approximate nearest neighbor search for $(\ell_p)^p$ metric, $0 < p < 1$

approximation-algorithms cg.comp-geom metrics metric-spaces

modified Oct 28 '19 at 23:35 Elliot Gorokhovsky 552

14

votes

1

answer

319

views

Why is the Greedy Conjecture so difficult?

reference-request approximation-algorithms greedy-algorithms

answered Oct 7 '19 at 21:02 Alex Golovnev 2,083

5

votes

0

answers

192

views

Martingale exit arguments for gradient Langevin dynamics

approximation-algorithms approximation stochastic-process

modified Sep 17 '19 at 0:13 Anirbit 614

3

votes

2

answers

167

views

What is the best approximation and exact algorithm for vertex cover on cubic graphs?

cc.complexity-theory ds.algorithms np-hardness complexity-classes approximation-algorithms

answered Sep 14 '19 at 10:52 A.2 136

2

votes

1

answer

144

views

About a pre-processing step for primal–dual weighted set cover problem

approximation-algorithms set-cover

modified Aug 22 '19 at 2:02 Community♦ 1

8

votes

1

answer

450

views

Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

ds.algorithms graph-theory co.combinatorics graph-algorithms approximation-algorithms

modified Aug 10 '19 at 21:36 Jianhao Ma 1

1

vote

0

answers

76

views

Alternative criterion for approximate maximum-weight perfect matching algorithms

approximation-algorithms randomized-algorithms matching bipartite-graphs

modified Jul 16 '19 at 21:40 prsm 19

6

votes

1

answer

68

views

NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family

approximation-algorithms approximation-hardness approximation csp np-intermediate

answered Jul 10 '19 at 17:48 Abel Molina 1,414

2

votes

0

answers

51

views

A “cut” packing problem

approximation-algorithms packing

asked Jul 10 '19 at 12:21 Mathieu Mari 421

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled