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

2

votes

1

answer

124

views

Approximation Ratio of Local search for $k-$center problem

approximation-algorithms clustering search-problem

modified Jul 26 at 7:40 Inuyasha Yagami 1,258

0

votes

1

answer

119

views

Minimum Degree Spanning Tree Without Restricting Vertices Searched

approximation-algorithms

modified Jul 24 at 7:07 Community♦ 1

3

votes

1

answer

180

views

$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

np-hardness approximation-algorithms packing extremal-combinatorics chernoff-bound

modified Jul 22 at 1:00 Community♦ 1

0

votes

1

answer

94

views

Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

co.combinatorics approximation-algorithms optimization linear-programming

answered Jul 18 at 3:36 Chandra Chekuri 6,325

0

votes

0

answers

50

views

Examples of SDP constant approximation algorithms on minimisation problems

approximation-algorithms optimization semidefinite-programming

modified Jul 15 at 20:28 Rodrigo de Azevedo 227

1

vote

0

answers

48

views

Failing to understand a lemma regarding Robust Low Rank Approximation

approximation-algorithms randomized-algorithms clustering

asked Jul 11 at 21:44 Sudipta Roy 169

1

vote

0

answers

39

views

Modifying sets to minimize the distance among each pair of the mean value of sets

np-hardness approximation-algorithms optimization

modified Jul 7 at 2:49 Refrain 45

0

votes

0

answers

43

views

Low Rank Approximation of a hidden subset

reference-request approximation-algorithms clustering

modified Jul 2 at 9:36 Sudipta Roy 169

0

votes

0

answers

35

views

A variant of k-median clustering

reference-request approximation-algorithms clustering

modified Jun 23 at 12:04 Sudipta Roy 169

1

vote

2

answers

151

views

Is there any Bi-criteria PTAS for Metric $k$-Median?

approximation-algorithms clustering

modified Jun 16 at 19:48 Neal Young 6,972

-1

votes

1

answer

223

views

Find research partner (profession and beginner)

graph-theory graph-algorithms approximation-algorithms optimization se.software-engineering

modified Jun 3 at 4:02 Tamas 39

2

votes

1

answer

119

views

Do there exist two equivalent objective functions one of which can be approximated but another one cannot?

ds.algorithms co.combinatorics approximation-algorithms approximation-hardness integer-programming

modified May 28 at 19:10 Neal Young 6,972

3

votes

0

answers

110

views

Incorrect Lower Bound of k-Means++ Algorithm

approximation-algorithms approximation-hardness clustering

modified May 16 at 19:01 Inuyasha Yagami 1,258

1

vote

2

answers

177

views

Two valued variant of subset sum problem

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

modified Apr 29 at 10:00 Community♦ 1

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled