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

Ask Question

more tags

Active 1 Bountied Hot Week Month

1

vote

0

answers

23

views

A continuum version of the 1D k-means clustering problem: constant factor approximations

approximation-algorithms clustering

asked Oct 19 at 0:59 Romans Pancs 33

1

vote

1

answer

29

views

Best approximations of Minimum Dominating Sets in chordal graphs

graph-algorithms approximation-algorithms approximation-hardness

modified Oct 16 at 17:58 daniello 2,991

13

votes

0

answers

365

views

Can we approximate the number of words accepted by an NFA?

ds.algorithms fl.formal-languages approximation-algorithms automata-theory counting-complexity

modified Oct 9 at 10:15 Corto 9

0

votes

0

answers

98

views

Algorithms and approximations for optimal offline binary tree operations

ds.algorithms approximation-algorithms optimization binary-trees

modified Sep 19 at 16:13 Mario Carneiro 133

7

votes

0

answers

81

views

Jump number approximation algorithm

approximation-algorithms partial-order

asked Aug 30 at 2:23 Gara Pruesse 332

1

vote

0

answers

64

views

Can the theory of Bidimensionality be applied to weighted instances of a problem?

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

asked Aug 26 at 19:27 Hao S 119

1

vote

0

answers

53

views

polytime approximability of directed multicut

reference-request approximation-algorithms approximation-hardness approximation max-flow-min-cut

asked Aug 24 at 18:29 user122938 21

12

votes

4

answers

737

views

Approximation algorithms used in exact algorithms

ds.algorithms big-list approximation-algorithms

modified Aug 12 at 20:42 Sariel Har-Peled 9,278

-1

votes

1

answer

61

views

approximate maximum clique given vertex cover

graph-algorithms approximation-algorithms reductions clique vertex-cover

modified Jul 21 at 17:07 Nicolas GZ 26

1

vote

2

answers

100

views

Where to find info on (polytime) approximability of various discrete optimization problems?

reference-request co.combinatorics approximation-algorithms optimization approximation-hardness

answered Jul 21 at 17:00 Nicolas GZ 26

6

votes

1

answer

130

views

Complexity of approximating a real function using queries

reference-request complexity-classes approximation-algorithms query-complexity computing-over-reals

modified Jul 20 at 10:30 Aryeh 8,544

6

votes

1

answer

146

views

Good Survey paper for k-means/k-median/k-center/facility-location

reference-request approximation-algorithms approximation-hardness clustering

answered Jul 9 at 4:14 Inuyasha yagami 635

0

votes

1

answer

104

views

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

approximation-algorithms set-cover average-case-complexity analysis-of-algorithms complexity-theory

modified Jun 27 at 20:45 David Eppstein 49.1k

9

votes

2

answers

3k

views

What are good approximation algorithms for the subset sum problem so far?

ds.algorithms np-hardness approximation-algorithms approximation-hardness subset-sum

answered Jun 16 at 18:18 dohmatob 213

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled