A PROCEDURE FOR COMPUTING THE K BEST SOLUTIONS TO DISCRETE OPTIMIZATION PROBLEMS AND ITS APPLICATION TO THE SHORTEST PATH PROBLEM

By E. Lawler. 1972

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Inferring the Why in Images (2014, methodology): “For both learning and evaluation, we require theK-best solutions, which can be done efficiently with approximate approaches such as K-best MAP estimation [3, 20] or sampling techniques [28, 25].”
Enumerate Lasso Solutions for Feature Selection (2017, methodology): “Our approach follows Lawler’s framework (Lawler 1972), which successively computes the optimal solution and then constructs subproblems that exclude the obtained optimal solution.”
The NP-Completeness Column: An Ongoing Guide (1982, unknown): “Moreover, even when K is arbitrary, the problem can be solved in pseudo-polynomial time (i.e., time polynomial in K and the size of the graph), using a general purpose technique due to Lawler [ 21 ] for generating the K best solutions to a 0-1 programming problem.”
Predicting Motivations of Actions by Leveraging Text (2014, methodology): “We often require the n-best solutions, which can be done efficiently with approximate approaches such as n-best MAP estimation [4, 21] or sampling techniques [28, 25].”
Multiple Choice Learning: Learning to Produce Multiple Structured Outputs (2012, methodology): “Traditionally, this is accomplished by learning a single-output model and then producing M -Best hypotheses from it (also called the M -Best MAP problem [20, 11, 29] or the Diverse M -Best problem [3] in the context of graphical models).”
Diverse M-Best Solutions in Markov Random Fields (2012, methodology): “Lawler [18] proposed a general algorithm to compute the top M solutions for a large family of discrete optimization problems, and the ideas used in Lawler’s algorithm form the basis of most algorithms for the M-Best MAP problem.”
Shortest-path kernels on graphs (2005, background): “Such algorithms have been proposed over 30 years ago [23, 15] and any of those can be run on our input graphs, as long as there are no cycles in our graphs with negative weights.”
Keyword Search in Relational Databases: A Survey (2010, methodology): “The algorithms are adaption of the Lawler’s procedure [20] to enumerate Q-SUBTREEs in rank order.”
An exact epsilon-constraint method for bi-objective combinatorial optimization problems: Application to the Traveling Salesman Problem with Profits (2009, methodology): “It relies on k-best algorithms [22], which have been developed for many problems such as the shortest path and minimum spanning tree problems.”
Approximate and Exact Enumeration of Rule Models (2018, methodology): “The algorithm is based on Lawler’s framework (Lawler 1972), which was previously used for enumerating feature selection re-sults (Hara and Maehara 2017).”