Explore our questions

2 votes
0 answers
29 views

Do prefix hash functions work well for approximate counting?

1 vote
0 answers
26 views

Is the Maximum Coverage Problem Remains as Hard when Taking Most Sets?

3 votes
0 answers
48 views

Partial Hamiltonian Path Optimization Problem

0 votes
2 answers
399 views

A k-approximation to k-way number partitioning

3 votes
1 answer
109 views

How well can shortest common supersequence over small alphabet size be approximated?

0 votes
0 answers
52 views

Shortest sequence that contains a given list of sequences as subsequences

2 votes
0 answers
75 views

References for algorithms to compute approximating polytopes for arbitrary convex sets

2 votes
1 answer
299 views

A non-trivial combinatorial optimization

5 votes
1 answer
186 views

What infinite sums cannot be approximated in polynomial time?

4 votes
0 answers
87 views

Working out the constants and probabilities of Stockmeyer's approximate counting algorithm

8 votes
1 answer
2k views

How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

2 votes
1 answer
101 views

Approximating the utilitarian welfare minus a constant

1 vote
1 answer
137 views

Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

2 votes
0 answers
37 views

Hardness of Coloring based on a Black-Box Hardness of Independent Set

Browse more Questions