Yishay Mansour, Baruch Schieber
Journal of Algorithms
Let G be a weighted, complete, directed acyclic graph whose edge weights obey the concave Monge condition. We give an efficient algorithm for finding the minimum weight k-link path between a given pair of vertices for any given k. The algorithm runs in n2o(√log k log n) time, for k = Ω(log n). 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 k-cliques of an interval graph, (4) finding the largest k-gon contained in a given convex polygon, (5) finding the smallest k-gon that is the intersection of k half-planes out of n half-planes defining a convex n-gon. © 1998 Academic Press.
Yishay Mansour, Baruch Schieber
Journal of Algorithms
Alexander Kesselman, Zvi Lotker, et al.
STOC 2001
Don Coppersmith, Baruch Schieber
FOCS 1992
Venkatesan T. Chakaravarthy, Michael Kapralov, et al.
IPDPS 2016