Theoretical Computer Science
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko's user avatar
Oleksandr Bondarenko
  • Member for 13 years, 2 months
  • Last seen more than a month ago
  • Kiev, Ukraine
Profile Activity

11 Questions

Score Activity Newest Views
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
522 views

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

17 votes
1 answer
367 views

Degree sets for linear extension graphs

15 votes
3 answers
614 views

Theories which characterize classes of computational complexity

12 votes
3 answers
588 views

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

10 votes
2 answers
340 views

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

9 votes
2 answers
7k views

Time complexity of Held-Karp algorithm for TSP

6 votes
1 answer
683 views

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

3 votes
3 answers
747 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 ?

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.