Stack Exchange

Oleksandr Bondarenko

Zaporizhzhya, Ukraine

phdprojectblog.blogspot.com

Age: 29

PhD student at Zaporizhzhya National University, Ukraine. Studying approximation algorithms for scheduling and packing problems.

top accounts reputation activity favorites subscriptions
Top Questions
18 votes

How to set LaTeX so that PDF reader opens PDF file in a prespecified view?

pdf viewers asked Apr 23 '11 at 19:55
tex.stackexchange.com

18 votes

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

ds.algorithms approximation-algorithms open-problem approximation-hardness scheduling asked Sep 13 '10 at 17:50
cstheory.stackexchange.com

17 votes

Degree sets for linear extension graphs

graph-theory co.combinatorics asked Nov 12 '10 at 0:52
cstheory.stackexchange.com

17 votes

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

ds.algorithms np-hardness np asked Jul 14 '11 at 18:11
cstheory.stackexchange.com

16 votes

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

ds.algorithms approximation-algorithms approximation-hardness asked Jan 27 '11 at 20:49
cstheory.stackexchange.com

15 votes

Theories which characterize classes of computational complexity

cc.complexity-theory reference-request complexity-classes lo.logic proof-complexity asked Jan 31 '11 at 13:17
cstheory.stackexchange.com

10 votes

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

ds.algorithms reference-request approximation-algorithms asked Dec 8 '10 at 22:39
cstheory.stackexchange.com

9 votes

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

cc.complexity-theory complexity-classes asked Sep 25 '10 at 12:37
cstheory.stackexchange.com

8 votes

Time complexity of Held-Karp algorithm for TSP

ds.algorithms tsp exp-time-algorithms asked Dec 6 '10 at 1:52
cstheory.stackexchange.com

7 votes

Why would definition not be proposition?

logic terminology asked Aug 17 '11 at 22:46
philosophy.stackexchange.com

1 2

Top Answers
25
Conjectures implying Four Color Theorem
cstheory.stackexchange.com

22
Ways for a mathematician to stay informed of current research in complexity theory
cstheory.stackexchange.com

18
Funny TCS-related papers etc?
cstheory.stackexchange.com

17
Collatz Conjecture & Grammars / Automata
cstheory.stackexchange.com

15
Polynomial time approximation algorithms for machine scheduling: how many open problems are left?
cstheory.stackexchange.com

13
What are the recent TCS books whose drafts are available online?
cstheory.stackexchange.com

12
Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?
cstheory.stackexchange.com

12
What is the tradeoff between population size and the number of generations in genetic algorithms
cstheory.stackexchange.com

12
Examples of hard instances for Goemans and Williamson algorithm
cstheory.stackexchange.com

12
Lovasz theta function and regular graphs (odd cycles in particular)
cstheory.stackexchange.com

11
Degree sets for linear extension graphs
cstheory.stackexchange.com

11
Graph planar drawing, with each edge's length is known
cstheory.stackexchange.com

10
Parameterized complexity from P to NP-hard and back again
cstheory.stackexchange.com

9
Is it possible to prove that, for a given problem, no optimal greedy algorithms exist?
cstheory.stackexchange.com

8
What are the problems with the best approximation ratio achieved by algorithm returning uniformly random solution?
cstheory.stackexchange.com

8
Time complexity of Bellman-Held-Karp algorithm for TSP, take 2
cstheory.stackexchange.com

8
What Books Should Everyone Read?
cstheory.stackexchange.com

8
Poly-time approximation scheme for problems with pseudo-polynomial time algorithms
cstheory.stackexchange.com

7
NP-Hardness of a special case of orthogonal packing problem
cstheory.stackexchange.com

7
Problems that are NP-complete under randomized or P/poly reductions.
cstheory.stackexchange.com

7
What are the recent TCS books whose drafts are available online?
cstheory.stackexchange.com

7
Is this a known combinatorial optimization/scheduling problem?
cstheory.stackexchange.com

6
How do you call a subsequence of consecutive elements ?
cstheory.stackexchange.com

6
Relation between fixed parameter and approximation algorithm
cstheory.stackexchange.com

6
Examples of #P problems which are in FP ?
cstheory.stackexchange.com

6
Problems Between P and NPC
cstheory.stackexchange.com

5
Hardness of approximation - additive error
cstheory.stackexchange.com

5
Problems Between P and NPC
cstheory.stackexchange.com