Approximation algorithms

Collections

Graph structure, approximation, counting and coordination across a network.

11 problems

7 total

How much can the best traveling-salesperson tour cost exceed its standard fractional relaxation in the worst metric instance?

Is it computationally hard to distinguish a graph with a small nearly isolated set from one where every equally small set strongly expands?

Can a fast algorithm always choose k vertices spanning within a fixed factor of the largest possible number of edges?

Can a polynomial-time algorithm remove all directed cycles while deleting at most a fixed multiple of the minimum possible vertex cost?

Can we efficiently estimate how many independent vertex sets an arbitrary bipartite graph has, with a guaranteed small relative error?

Can a polynomial-time algorithm find a tree decomposition whose largest bag is within a fixed factor of the smallest possible?