Computing a minimum-weight κ-link path in graphs with the concave monge property

Abstract

Let G be a weighted, complete, directed acyclic graph (DAG) whose edge weights obey the concave Monge condition. We give an efficient algorithm for finding the minimum-weight κ-link path between a given pair of vertices for any given κ. The algorithm runs in n2O(√logκloglogn) time Our algorithm can be applied to get efficient solutions for the following problems, improving on previous results: (1) computing length-limited Huffman codes. (2) computing optimal discrete quantization. (3) computing maximum κ-chques of an interval graph. (4) finding the largest κ-gon contained in a given convex polygon. (5) finding the smallest κ-gon that is the intersection of κ half-planes out of n half-planes defining a convex n-gon.