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

20

views

Complexity of approximating a real function using queries

reference-request complexity-classes approximation-algorithms query-complexity computing-over-reals

asked 10 hours ago Erel Segal-Halevi 1,480

5

votes

1

answer

122

views

Good Survey paper for k-means/k-median/k-center/facility-location

reference-request approximation-algorithms approximation-hardness clustering

answered Jul 9 at 4:14 Inuyasha yagami 615

0

votes

1

answer

98

views

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

approximation-algorithms set-cover average-case-complexity analysis-of-algorithms complexity-theory

modified Jun 27 at 20:45 David Eppstein 48.6k

9

votes

2

answers

3k

views

What are good approximation algorithms for the subset sum problem so far?

ds.algorithms np-hardness approximation-algorithms approximation-hardness subset-sum

answered Jun 16 at 18:18 dohmatob 151

-1

votes

0

answers

33

views

Application of a Poisson inequality in the networks

ds.algorithms approximation-algorithms network-modeling

asked Jun 14 at 15:10 user124297 139

9

votes

1

answer

330

views

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

graph-theory approximation-algorithms optimization approximation-hardness approximation

modified Jun 12 at 15:03 Yury 3,726

1

vote

0

answers

62

views

Separation oracle for hitting all small cut on a graph?

approximation-algorithms linear-programming integer-programming

modified Jun 2 at 5:45 Mengfan Ma 365

2

votes

1

answer

71

views

kmeans++ for arbitrary metric spaces and general potential function

approximation-algorithms randomized-algorithms clustering metric-spaces

answered May 26 at 0:54 Neal Young 6,025

3

votes

1

answer

97

views

Additive versus multiplicative accuracy

approximation-algorithms

modified May 24 at 15:54 Neal Young 6,025

0

votes

0

answers

33

views

Different version of approximation complexity and algorithm for densest-k-subgraph problem

graph-theory approximation-algorithms approximation-hardness

asked May 24 at 12:51 郑炜强 1

6

votes

1

answer

498

views

Maximizing difference of a submodular and a modular function

ds.algorithms approximation-algorithms optimization submodularity

answered May 18 at 23:01 dohmatob 151

6

votes

1

answer

505

views

Ordering of a DAG minimizing some definition of cost

graph-theory approximation-algorithms directed-acyclic-graph topological-sorting

modified May 15 at 15:55 a3nm 6,766

1

vote

1

answer

64

views

How can I find dependent rounding procedures with the desirable properties?

reference-request approximation-algorithms

answered May 7 at 22:02 Chandra Chekuri 6,016

0

votes

0

answers

30

views

Polynomial time multiplicative approximation algorithms for logistic regression?

approximation-algorithms

asked May 1 at 6:13 Television 111

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled