Skip to main content
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko
  • Member for 13 years, 9 months
  • Last seen more than a month ago
  • Kiev, Ukraine
9 votes
2 answers
7k views

Time complexity of Held-Karp algorithm for TSP

22 votes
2 answers
2k 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?

3 votes
3 answers
751 views

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

6 votes
1 answer
683 views

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

15 votes
3 answers
620 views

Theories which characterize classes of computational complexity

12 votes
3 answers
589 views

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

17 votes
3 answers
530 views

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

17 votes
1 answer
370 views

Degree sets for linear extension graphs

10 votes
2 answers
346 views

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

2 votes
0 answers
169 views

References for the mathematical safe problem ?