Explore Our Questions

more tags

Active Hot Week Month

2

votes

1

answer

126

views

About a pre-processing step for primal–dual weighted set cover problem

approximation-algorithms set-cover

modified yesterday Community♦ 1

-1

votes

0

answers

17

views

Why define “relaxed optimality conditions” this way for Fractional Packing and Covering Problems?

approximation-algorithms linear-programming packing covering-problems

asked 2 days ago Varun Ramanathan 1

-1

votes

2

answers

62

views

Machine Learning Algorithm To Fill Data Holes

approximation-algorithms machine-learning ai.artificial-intel

answered Apr 18 at 19:48 Anonymous 11

17

votes

1

answer

453

views

Approximation for counting the number of simple $s$-$t$ paths in a general graph

ds.algorithms reference-request graph-algorithms approximation-algorithms counting-complexity

answered Apr 12 at 5:44 Heng Guo 341

-2

votes

0

answers

32

views

minimizing monotone submodular function with cardinality constraints without non negativeness

reference-request approximation-algorithms submodularity

asked Apr 11 at 4:24 user49739 1

1

vote

0

answers

38

views

Stable recovery of signals by $\ell_1$ optimization

reference-request approximation-algorithms sparse-matrix compressed-sensing stable

asked Apr 8 at 20:17 gradstudent 718

34

votes

1

answer

1k

views

Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

ds.algorithms approximation-algorithms linear-programming primal-dual semidefinite-programming

modified Apr 5 at 21:06 Neal Young 4,324

3

votes

1

answer

128

views

Intuitive explanation behind Goemans-Williamson randomized rounding

approximation-algorithms optimization randomized-algorithms max-cut

modified Mar 16 at 16:49 Rodrigo de Azevedo 174

0

votes

2

answers

871

views

Is the current best approximation ratio for Vertex Cover problem also a lower bound?

approximation-algorithms approximation-hardness

answered Mar 15 at 20:59 Yuval Filmus 13.3k

7

votes

1

answer

106

views

Smoothed analysis to compare algorithms

ds.algorithms approximation-algorithms smoothed-analysis

answered Feb 11 at 11:40 Bodo Manthey 355

5

votes

1

answer

311

views

Do combinatorial discrepancy upper bounds lead to smaller $\epsilon$-nets (as with $\epsilon$-samples)?

cg.comp-geom approximation-algorithms vc-dimension

modified Feb 11 at 8:46 Jan Johannsen 3,874

44

votes

4

answers

12k

views

Approximation algorithms for Metric TSP

cc.complexity-theory graph-algorithms approximation-algorithms tsp exp-time-algorithms

modified Jan 25 at 3:01 Alex Golovnev 1,353

2

votes

0

answers

65

views

What is the competitive ratio of a $d$-way associative LRU cache?

ds.algorithms approximation-algorithms online-algorithms competitive-ratio

asked Jan 14 at 20:34 R B 6,294

2

votes

1

answer

92

views

Maximum-minimum satisfiability

approximation-algorithms optimization sat

answered Jan 9 at 20:43 james 36

Browse More Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled