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

5

answers

516

views

Submodular functions: reference request

ds.algorithms reference-request approximation-algorithms optimization

answered Mar 24 at 12:03 user56394 1

-1

votes

0

answers

22

views

Evolving expression trees to approximate an unknown function

ds.algorithms approximation-algorithms randomized-algorithms tree ne.neural-evol

asked Mar 22 at 20:05 void 99

2

votes

0

answers

87

views

Complexity of a scheduling problem with a fixed left bound of jobs

cc.complexity-theory reference-request np-hardness approximation-algorithms approximation-hardness

modified Mar 5 at 23:32 Siddha 3

3

votes

1

answer

126

views

Is this greedy algorithm for vertex cover studied before?

reference-request approximation-algorithms greedy-algorithms

answered Feb 9 at 10:42 Yixin Cao 2,185

-2

votes

1

answer

320

views

Sequential vs Distributed algo question

graph-algorithms approximation-algorithms dc.distributed-comp polynomial-time

modified Feb 5 at 10:57 Arnaud Casteigts 192

9

votes

5

answers

433

views

W[1]-hard problems with FPT time approximation algorithms

ds.algorithms approximation-algorithms parameterized-complexity fixed-parameter-tractable

modified Jan 29 at 17:06 Amir Nikabadi 51

-1

votes

1

answer

65

views

the shorstest cycle containing two given points

cc.complexity-theory approximation-algorithms approximation-hardness planar-graphs

answered Jan 23 at 19:43 David Eppstein 47.8k

4

votes

1

answer

949

views

Is an algorithm with an approximation factor of 4000 useful?

approximation-algorithms approximation

modified Jan 12 at 7:37 Hermann Gruber 4,359

5

votes

0

answers

58

views

Relaxed minimum dominating set

approximation-algorithms randomized-algorithms integer-programming

modified Dec 12 '19 at 10:38 AmeerJ 587

6

votes

1

answer

223

views

What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?

ds.algorithms graph-algorithms approximation-algorithms exp-time-algorithms

modified Dec 6 '19 at 1:25 R B 9,085

0

votes

0

answers

58

views

What is the run-time of LP?

approximation-algorithms time-complexity linear-programming

modified Nov 11 '19 at 1:16 gradstudent 1,391

0

votes

0

answers

39

views

Approximate nearest neighbor search for $(\ell_p)^p$ metric, $0 < p < 1$

approximation-algorithms cg.comp-geom metrics metric-spaces

modified Oct 28 '19 at 23:35 Elliot Gorokhovsky 552

14

votes

1

answer

344

views

Why is the Greedy Conjecture so difficult?

reference-request approximation-algorithms greedy-algorithms

answered Oct 7 '19 at 21:02 Alex Golovnev 2,083

5

votes

0

answers

215

views

Martingale exit arguments for gradient Langevin dynamics

approximation-algorithms approximation stochastic-process

modified Sep 17 '19 at 0:13 Anirbit 614

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled