Two-best solutions under distance constraints: The model and exemplary results for matroids

DOI10.1006/AAMA.1998.0618MaRDI QIDQ1291060zbMATH OpenOpenAlexFDO

Authors Ingo Althöfer, Walter Wenzel

Publication date 11 October 1999

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/aama.1998.0618

zbMATH Keywords

distance functionorientable matroidvaluated matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Review text

The authors investigate \(k\)-best questions with distance constraints \((k=2)\), deriving several results for valuated matroids. As a distance function on the set of all bases in a matroid the following function is taken: \(d(B_1, B_2)= {1\over 2}[\text{card}(B_1\setminus B_2)+ \text{card}(B_2\setminus B_1)]\). Two examples with maximum spanning trees in a medium size graph are discussed together with several ideas on \(k\)-best solutions.

Recommendations

• \(k\)-best solutions under distance constraints in valuated \(\Delta\)-matroids
• k-Best constrained bases of a matroid
• On the \(K\)th best base of a matroid
• A polynomial algorithm for finding a prescribed number of best solutions of extremal problems on matroids

Cites work

• A dynamic programming algorithm to find all solutions in a neighborhood of the optimum
• A Method for the Solution of the N th Best Path Problem
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• An Algorithm for Finding K Minimum Spanning Trees
• Finding the \(k\) quickest simple paths in a network
• Finding the k Shortest Paths
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 53152 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 480249 (Why is no real title available?)
• Intersection of Two Matroids: (Condensed) Border Graphs and Ranking
• k-optimal solution sets for some polynomially solvable scheduling problems
• Maurer's homotopy theory for even \(\Delta\)-matroids and related combinatorial geometries
• Minimal-energy clusters of hard spheres
• Onkth Best Policies
• Penny-packing and two-dimensional codes
• Sequence alignments in the neighborhood of the optimum with general application to dynamic programming
• Solving the Fixed Charge Problem by Ranking the Extreme Points
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• Valuated matroids
• Valuated matroids: A new look at the greedy algorithm

Cited in

(5)

• \(k\)-best solutions under distance constraints in valuated \(\Delta\)-matroids
• A polynomial algorithm for finding a prescribed number of best solutions of extremal problems on matroids
• k-Best constrained bases of a matroid
• On circuit valuation of matroids
• On the \(K\)th best base of a matroid

This page was built for publication: Two-best solutions under distance constraints: The model and exemplary results for matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1291060)