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

302

views

Find research partner (profession and beginner)

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

modified Jan 12 at 14:53 Deepak kamalta 1

1

vote

1

answer

162

views

2-Center problem with forbidden pairs

ds.algorithms approximation-algorithms

answered Jan 4 at 14:40 Neal Young 7,598

4

votes

0

answers

79

views

Hashing-based vs almost uniform sampling-based approximate counting

approximation-algorithms quantum-computing counting-complexity randomized-algorithms approximation-hardness

asked Dec 23 '21 at 16:17 delete000 738

0

votes

1

answer

178

views

A k-approximation to k-way number partitioning

approximation-algorithms partition-problem

modified Dec 19 '21 at 15:05 CommunityBot 1

5

votes

2

answers

461

views

Max cut problem between two connected subgraphs

cc.complexity-theory reference-request graph-algorithms approximation-algorithms randomized-algorithms

modified Dec 7 '21 at 16:52 Tianqi Ma 1

4

votes

1

answer

104

views

A counter example for the set mean objective

reference-request approximation-algorithms computational-geometry clustering

answered Dec 1 '21 at 16:53 Inuyasha Yagami 1,369

5

votes

1

answer

229

views

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

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

modified Nov 19 '21 at 1:00 CommunityBot 1

20

votes

1

answer

409

views

What are the best possible time/error tradeoffs for approximate solution of linear programs?

ds.algorithms approximation-algorithms online-learning linear-programming

modified Nov 13 '21 at 21:28 Neal Young 7,598

16

votes

1

answer

476

views

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

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

answered Nov 8 '21 at 2:23 ricardorr 521

2

votes

1

answer

99

views

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

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

modified Nov 6 '21 at 3:07 CommunityBot 1

0

votes

0

answers

59

views

Minimize Cumulative Cost on Topological Sort

ds.algorithms approximation-algorithms directed-acyclic-graph topological-sorting

modified Nov 5 '21 at 12:16 msalichs 9

1

vote

0

answers

44

views

Approximate solution for maximum coverage problem with choice constraint

ds.algorithms graph-theory graph-algorithms co.combinatorics approximation-algorithms

asked Nov 2 '21 at 3:46 Rise of Kingdom 67

3

votes

0

answers

69

views

Bin packing where each item must occur in $k$ bins

approximation-algorithms optimization packing

asked Oct 29 '21 at 9:17 Erel Segal-Halevi 1,722

0

votes

0

answers

36

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 '21 at 7:44 Karagounis Z 503

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled