We’re rewarding the question askers & reputations are being recalculated! Read more.

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 1 Bountied Hot Week Month

-2

votes

0

answers

35

views

Can Christofides algorithm provide different solution in different execution?

graph-algorithms approximation-algorithms tsp

asked Nov 15 at 14:05 LSG 97

0

votes

0

answers

48

views

What is the run-time of LP?

approximation-algorithms time-complexity linear-programming

modified Nov 11 at 1:16 gradstudent 1,323

0

votes

0

answers

37

views

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

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

modified Oct 28 at 23:35 Elliot Gorokhovsky 552

14

votes

1

answer

292

views

Why is the Greedy Conjecture so difficult?

reference-request approximation-algorithms greedy-algorithms

answered Oct 7 at 21:02 Alex Golovnev 2,063

5

votes

0

answers

169

views

Martingale exit arguments for gradient Langevin dynamics

approximation-algorithms approximation stochastic-process

modified Sep 17 at 0:13 Anirbit 614

3

votes

2

answers

158

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 at 10:52 A.2 96

3

votes

1

answer

102

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

answered Sep 6 at 22:31 A.2 96

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 at 2:02 Community♦ 1

8

votes

1

answer

444

views

Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

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

modified Aug 10 at 21:36 Jianhao Ma 1

1

vote

0

answers

71

views

Alternative criterion for approximate maximum-weight perfect matching algorithms

approximation-algorithms randomized-algorithms matching bipartite-graphs

modified Jul 16 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 at 17:48 Abel Molina 1,404

2

votes

0

answers

50

views

A “cut” packing problem

approximation-algorithms packing

asked Jul 10 at 12:21 Mathieu Mari 405

2

votes

0

answers

81

views

What is the communication complexity of approximating addition?

approximation-algorithms circuit-complexity communication-complexity circuit-depth

asked Jun 27 at 1:59 exfret 533

0

votes

1

answer

84

views

finding maximum weight subgraph

graph-theory graph-algorithms approximation-algorithms linear-programming

answered Jun 25 at 19:41 Yonatan N 1,301

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled