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

31

votes

5

answers

12k

views

Complexity of the simplex algorithm

ds.algorithms linear-programming simplex smoothed-analysis

modified 7 hours ago VS. 79

21

votes

10

answers

2k

views

#SAT Solver download

ds.algorithms sat software

answered 2 days ago holf 1,171

2

votes

1

answer

57

views

Reconstruction of a sequence generated by a Markov chain - reference request

ds.algorithms pr.probability lg.learning markov-chains bioinformatics

answered 2 days ago Aryeh 6,212

3

votes

2

answers

156

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

0

votes

0

answers

53

views

Generalization of k-Coloring: maximizing the number of vertices with no neighbours of same color

ds.algorithms graph-theory np-hardness graph-colouring max-cut

asked Sep 7 at 19:02 Dan 41

3

votes

1

answer

84

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

7

votes

2

answers

2k

views

Proof of Levenshtein distance

ds.algorithms proofs edit-distance

modified Sep 3 at 17:59 Jeffε 18.4k

18

votes

11

answers

2k

views

Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

ds.algorithms big-list time-complexity

modified Sep 3 at 14:47 SamM 1,247

4

votes

1

answer

677

views

Knapsack with dependent profits (pairs of items)

ds.algorithms optimization

modified Sep 1 at 9:02 Community♦ 1

2

votes

1

answer

162

views

How many samples are needed to reconstruct a path?

ds.algorithms graph-theory graph-algorithms machine-learning sample-complexity

modified Aug 29 at 8:16 Assosa Ethiopia 1

-2

votes

1

answer

81

views

An efficient algorithm for maximizing gain by choosing from a set of options

ds.algorithms

modified Aug 27 at 12:41 generic_user 97

4

votes

1

answer

126

views

Consequences/existence of problems without any “optimal” algorithm

ds.algorithms complexity-classes time-complexity

answered Aug 21 at 3:43 Will Angley 156

0

votes

2

answers

370

views

Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

ds.algorithms optimization

answered Aug 19 at 23:25 Peter Taylor 1,225

10

votes

2

answers

466

views

Lattice problems

ds.algorithms reference-request graph-algorithms partial-order order-theory

answered Aug 19 at 17:24 user53561 11

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled