Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko
  • Member for 12 years
  • Last seen more than a month ago
  • Kiev, Ukraine
22 votes
2 answers
1k views

Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

19 votes
2 answers
1k views

Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

17 votes
3 answers
510 views

Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?

17 votes
1 answer
362 views

Degree sets for linear extension graphs

15 votes
3 answers
605 views

Theories which characterize classes of computational complexity

12 votes
3 answers
580 views

What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?

10 votes
2 answers
327 views

Is there known any complexity class containing online counterparts of optimization problems?

9 votes
2 answers
6k views

Time complexity of Held-Karp algorithm for TSP

6 votes
1 answer
678 views

Lower bound on independence number in terms of clique number and order of graph

3 votes
3 answers
740 views

Can we partition NP-complete problem into finite number of polynomially solvable problems?

2 votes
0 answers
169 views

References for the mathematical safe problem ?