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

1

vote

2

answers

156

views

Two valued variant of subset sum problem

np-hardness approximation-algorithms partition-problem subset-sum

modified Apr 29 at 10:00 Community♦ 1

0

votes

1

answer

129

views

A k-approximation to k-way number partitioning

approximation-algorithms partition-problem

modified Apr 23 at 14:03 Community♦ 1

4

votes

2

answers

152

views

kmeans++ for arbitrary metric spaces and general potential function

approximation-algorithms randomized-algorithms clustering metric-spaces

answered Apr 4 at 15:39 Sudipta Roy 163

3

votes

1

answer

85

views

Approximating Independent Dominating set on bipartite graphs

reference-request graph-algorithms approximation-algorithms approximation-hardness

answered Mar 26 at 22:50 Tassle 131

0

votes

1

answer

90

views

Minimum Degree Spanning Tree Without Restricting Vertices Searched

approximation-algorithms

modified Mar 26 at 7:01 Community♦ 1

9

votes

1

answer

496

views

Is the following graph optimization problem approximable within a constant factor?

graph-theory approximation-algorithms optimization approximation-hardness approximation

modified Mar 17 at 14:56 maxdan94 493

2

votes

0

answers

61

views

Is there a name for approximation algorithms with $f(OPT)$ approximation factor?

approximation-algorithms

asked Mar 16 at 20:34 jesús garcía 21

11

votes

2

answers

3k

views

Integer Factoring via Lattice Reduction?

ds.algorithms approximation-algorithms integer-programming

modified Mar 4 at 10:37 fbmm 1

3

votes

0

answers

75

views

Improving the approximation in Stockmeyer's counting theorem

cc.complexity-theory complexity-classes approximation-algorithms counting-complexity approximation-hardness

asked Mar 1 at 4:26 AngryLion 91

0

votes

0

answers

24

views

Given an input sequence of real numbers, how to find the closest sequence in a large set of sequences

reference-request approximation-algorithms ds.data-structures randomized-algorithms

asked Feb 23 at 14:41 Penelope Benenati 101

2

votes

1

answer

463

views

The non-metric k-median problem

approximation-algorithms approximation-hardness clustering

modified Feb 22 at 12:34 Inuyasha Yagami 807

10

votes

1

answer

333

views

Is subtractive dithering the optimal algorithm for sending a real number using one bit?

ds.algorithms approximation-algorithms it.information-theory coding-theory encoding

modified Feb 14 at 2:42 zeb 351

1

vote

1

answer

45

views

What is the run-time of the bin packing approximation algorithm?

approximation-algorithms time-complexity

modified Feb 11 at 17:15 Erel Segal-Halevi 1,618

2

votes

0

answers

51

views

Hessian of non differentiable convex function

reference-request approximation-algorithms convex-optimization

modified Jan 29 at 5:31 Sudipta Roy 163

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled