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

0

votes

0

answers

31

views

Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?

reference-request graph-theory graph-algorithms approximation-algorithms optimization

asked Oct 21 at 7:44 Karagounis Z 473

0

votes

0

answers

48

views

k-Median Problem With Restricted Centers

approximation-algorithms clustering

asked Oct 18 at 19:30 Inuyasha Yagami 1,306

-1

votes

2

answers

243

views

Partition a graph into two clusters

ds.algorithms graph-theory approximation-algorithms

modified Oct 15 at 12:51 Neal Young 7,397

0

votes

1

answer

119

views

Finding top-K items in a sliding window

approximation-algorithms sorting data-streams streaming-algorithms

modified Oct 13 at 13:01 CommunityBot 1

1

vote

1

answer

160

views

State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

graph-theory graph-algorithms approximation-algorithms approximation max-cut

answered Oct 9 at 20:46 Jukka Suomela 11.2k

2

votes

1

answer

72

views

Can this special case of Node Weighted Steiner Tree be solved in polynomial time?

graph-theory graph-algorithms np-hardness approximation-algorithms

modified Oct 7 at 2:24 Karagounis Z 473

-1

votes

0

answers

60

views

A Special case of Weighted Set Cover Problem

approximation-algorithms set-cover

modified Oct 3 at 16:10 Arash Vaezi 1

1

vote

2

answers

249

views

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

approximation-algorithms clustering

modified Sep 29 at 18:57 Inuyasha Yagami 1,306

0

votes

1

answer

153

views

A k-approximation to k-way number partitioning

approximation-algorithms partition-problem

modified Aug 21 at 14:07 CommunityBot 1

0

votes

0

answers

42

views

Using bin-packing algorithms to approximate maximum-makespan

approximation-algorithms optimization partition-problem scheduling packing

modified Aug 18 at 11:33 Erel Segal-Halevi 1,640

3

votes

1

answer

154

views

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

approximation-algorithms clustering search-problem

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

0

votes

1

answer

122

views

Minimum Degree Spanning Tree Without Restricting Vertices Searched

approximation-algorithms

modified Jul 24 at 7:07 CommunityBot 1

3

votes

1

answer

189

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 CommunityBot 1

0

votes

1

answer

114

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,430

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled