Open Questions

Here are some open questions that interest me. I intend to expand this list in the future.

Is there a sub-cubic algorithm for the Hitchcock-Koopmans Transportation Problem when the underlying cost function is a metric? The well-known Hungarian method takes cubic time to compute the optimal solution -- however better algorithms are known for some special cases like the one described in Gabow and Tarjan's paper.

Is there a sub-cubic algorithm to compute minimum matching in a weighted bipartite graph with real valued edge costs? Minimum-cost bipartite matching can be computed in O(n³) time when the cost of edges are arbitrary real values. However, when the edge costs are positive integers bounded by k, using scaling technique introduced in Gabow and Tarjan's paper, minimum-cost matching can be computed in O(n^2.5log k) time. Consider the special case where vertices of the graph are d dimensional points with bounded integer coordinates and the cost of an edge is the Euclidean distance between its end-points -- there is no obvious way of applying scaling technique to even this special case. In 2d, this paper obtains a faster algorithm by exploiting the scaling technique along with the geometry of the input points.

Is there a PTAS for approximating Minimum Weight Triangulation of a 2 dimensional point set? Among others, Minimum Weight Triangulation, Minimum Euclidean Bipartite Matching and Minimum Euclidean Bipartite Traveling Salesman Problem seem resistant to the well-known Arora's method for geometric approximation algorithms. In this paper we give near-linear approximation algorithm for Minimum Euclidean Bipartite Matching -- the other problems, however, remain open.

Please drop me an email if you have any interesting ideas or papers related to these topics. Thanks!

Back