Some basic exchange properties in combinatorial optimization and their application to constructing the k-best solutions
type: Item
instance of: scholarly article
title: Some basic exchange properties in combinatorial optimization and their application to constructing the k-best solutions
zbMATH Open document ID: 0573.90070
DOI: 10.1016/S0166-218X(85)80004-4
author: Ulrich Derigs
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: For a certain class of combinatorial optimization problems the author introduces an exchange pairs (EP) set. Using the EP set the author constructs some sort of gradient and solves the problem by a variant of a greedy method. The computational complexity of the greedy method depends heavily on the complexity of constructing a generation set for the EP set.
Mathematics Subject Classification ID: 90C09
zbMATH DE Number: 3916022
zbMATH Keywords: k-best solutions
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: exchange properties
zbMATH Keywords: adjacency
zbMATH Keywords: gradient
zbMATH Keywords: greedy method
reviewed by: M. A. Frumkin
MaRDI profile type: Publication
cites work: Q4091421
cites work: Thek best spanning arborescences of a network
cites work: Q3037095
cites work: Q4197644
cites work: Two Algorithms for Generating Weighted Spanning Trees in Order
cites work: An Algorithm for Finding K Minimum Spanning Trees
cites work: A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
cites work: Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
cites work: The travelling salesman problem and a class of polyhedra of diameter two
cites work: Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
description: scientific article; zbMATH DE number 3916022