Adjacency on polymatroids

DOI10.1007/BF02591887MaRDI QIDQ3335528zbMATH OpenFDO

Authors Donald M. Topkis

Publication date 1984

Published in Mathematical Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02591887

zbMATH Keywords

adjacency for extreme pointsconvex gamepolymatroidpolynomial algorithmsubmodular function

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Polytopes and polyhedra (52Bxx) Integer programming (90C10)

Recommendations

• The Partial Order of a Polymatroid Extreme Point
• An extreme point theorem for ordered polymatroids on chain orders
• A polymatroid associated with convex games
• On matroid intersection adjacency
• scientific article; zbMATH DE number 3906513

Cites work

• Activity selection games and the minimum‐cut problem
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• Adjacency on Convex Polyhedra
• Adjacency on the Postman Polyhedron
• Adjacent vertices of the all 0-1 programming polytope
• Adjacent Vertices on a Permutohedron
• Adjacent vertices on the b-matching polyhedron
• Adjacent vertices on transportation polytopes
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
• Characterizations of adjacency on the branching polyhedron
• Cores of convex games
• Determining adjacent vertices on assignment polytopes
• scientific article; zbMATH DE number 3659288 (Why is no real title available?)
• scientific article; zbMATH DE number 3659595 (Why is no real title available?)
• scientific article; zbMATH DE number 3687081 (Why is no real title available?)
• scientific article; zbMATH DE number 3749025 (Why is no real title available?)
• scientific article; zbMATH DE number 3628719 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• On certain polytopes associated with graphs
• On the Set-Covering Problem
• On the Set-Covering Problem: II. An Algorithm for Set Partitioning
• On the Tours of a Traveling Salesman
• Some properties of the assignment polytope
• The adjacency relation on the traveling salesman polytope is NP-Complete
• The ellipsoid method and its consequences in combinatorial optimization
• The Partial Order of a Polymatroid Extreme Point
• The travelling salesman problem and a class of polyhedra of diameter two

Cited in

(21)

• Ehrhart polynomials of matroid polytopes and polymatroids
• Generalized polymatroids and submodular flows
• Two algorithms for maximizing a separable concave function over a polymatroid feasible region
• Paths on polymatroids
• The polytope of win vectors
• Adjacency of the best and second best valued solutions in combinatorial optimization problems
• An extreme point theorem for ordered polymatroids on chain orders
• Adjacency on the order polytope with applications to the theory of fuzzy measures
• Extended formulations for matroid polytopes through randomized protocols
• Circuit walks in integral polyhedra
• Adjacency polynomials of digraph transformations
• The fundamental theorem of linear programming: extensions and applications
• scientific article; zbMATH DE number 3906512 (Why is no real title available?)
• The Partial Order of a Polymatroid Extreme Point
• On the length of monotone paths in polyhedra
• On the expansion of combinatorial polytopes
• One-adhesive polymatroids.
• A normal fan projection algorithm for low-rank optimization
• Hardness of finding combinatorial shortest paths on graph associahedra
• Combinatorics of generalized parking-function polytopes
• A note on Frank's generalized polymatroids

This page was built for publication: Adjacency on polymatroids

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