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

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

2

votes

0

answers

59

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 59

0

votes

1

answer

58

views

Minimum Degree Spanning Tree Without Restricting Vertices Searched

approximation-algorithms

modified Feb 24 at 6:08 user3508551 319

0

votes

0

answers

20

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

442

views

The non-metric k-median problem

approximation-algorithms approximation-hardness clustering

modified Feb 22 at 12:34 Inuyasha Yagami 757

10

votes

1

answer

298

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 341

1

vote

1

answer

44

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

46

views

Hessian of non differentiable convex function

reference-request approximation-algorithms convex-optimization

modified Jan 29 at 5:31 Sudipta Roy 153

0

votes

0

answers

37

views

are there approximation algorithms that use primal-dual with LP values and/or rounding?

co.combinatorics approximation-algorithms linear-programming primal-dual iterated-rounding

modified Jan 27 at 21:24 Hao S 199

1

vote

0

answers

63

views

Hardness of Approximation of Continuous Metric k-Median

approximation-algorithms approximation-hardness set-cover clustering

modified Jan 15 at 21:35 Inuyasha Yagami 757

0

votes

1

answer

107

views

A k-approximation to k-way number partitioning

approximation-algorithms partition-problem

modified Dec 24 '20 at 13:02 Community♦ 1

0

votes

0

answers

46

views

Balanced and general $MAXkSAT$ known approximation results and bounds from $UGC$

cc.complexity-theory approximation-algorithms approximation-hardness unique-games-conjecture max2sat

modified Nov 28 '20 at 15:11 1.. 11.6k

9

votes

1

answer

3k

views

What's the approximation factor of this Max k-Cut approximation?

ds.algorithms graph-algorithms approximation-algorithms max-cut

modified Nov 25 '20 at 9:58 Saeed 3,393

1

vote

0

answers

29

views

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

approximation-algorithms clustering

asked Oct 19 '20 at 0:59 Romans Pancs 33

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled