Metric TSP subtour integrality gap
How much can the best traveling-salesperson tour cost exceed its standard fractional relaxation in the worst metric instance?
Approximation algorithms
Within Approximation algorithms · Search all subjects
Small-Set Expansion hypothesis
Is it computationally hard to distinguish a graph with a small nearly isolated set from one where every equally small set strongly expands?
Densest-k-subgraph approximation
Can a fast algorithm always choose k vertices spanning within a fixed factor of the largest possible number of edges?
Directed feedback vertex set approximation
Can a polynomial-time algorithm remove all directed cycles while deleting at most a fixed multiple of the minimum possible vertex cost?
#BIS approximability
Can we efficiently estimate how many independent vertex sets an arbitrary bipartite graph has, with a guaranteed small relative error?
Constant-factor treewidth approximation
Can a polynomial-time algorithm find a tree decomposition whose largest bag is within a fixed factor of the smallest possible?
Online bin packing competitive ratio
Items arrive one at a time and must be placed immediately into unit-capacity bins. What is the smallest guaranteed long-run overhead compared with packing the whole list after seeing it?