Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore our questions

5 votes
1 answer
169 views

Hashing-based vs almost uniform sampling-based approximate counting

2 votes
0 answers
43 views

Submodular welfare maximization: what is the best known approximation ratio of a deterministic algorithm?

0 votes
0 answers
21 views

Maximum independent set in "subgraph-claw-free" graphs

0 votes
1 answer
63 views

Proper terminology for input, parameter or variable fixing. Refinement? Projection? Fixation? Partial valuation?

0 votes
1 answer
260 views

A k-approximation to k-way number partitioning

0 votes
2 answers
344 views

Partition a graph into two clusters

0 votes
0 answers
22 views

Is there a theoretical runtime guarantee to eigen decomposition (up to some convergence distance)?

1 vote
0 answers
49 views

Better approximation of the subset in the membership oracle

0 votes
1 answer
157 views

The Complexity of Multi-Objective Optimization

1 vote
0 answers
66 views

How to enforce convexity?

15 votes
1 answer
941 views

Integer relation detection for Subset Sum or NPP?

6 votes
1 answer
132 views

Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$

0 votes
0 answers
60 views

Approximation algorithm for maximum independent set of squares

0 votes
0 answers
45 views

Can one obtain an FPTAS for Knapsack by Rounding Weights (and not Profits)?

Browse more Questions