Adjacency on the constrained assignment problem

DOI10.1016/S0166-218X(98)00063-8MaRDI QIDQ1270787zbMATH OpenOpenAlexFDO

Authors Abdo Y. Alfakih, Katta G. Murty

Publication date 3 November 1998

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

adjacency checkingAlfakihassignment polytopeconstrained assignmentinteger hullMurty

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The -connected assignment problem
• On the configuration-LP of the restricted assignment problem
• scientific article; zbMATH DE number 30946
• Constrained matching problems in bipartite graphs
• The constrained minimax linear assignment problem
• Optimal Assignments for Consecutive-2 Graphs
• Constructing And Selecting Adjacency Constraints
• Closest assignment constraints in discrete location problems
• scientific article; zbMATH DE number 4108497
• On imposing connectivity constraints in integer programs

Cites work

• A remark on the faces of the cone of Euclidean distance matrices
• Adjacency on Convex Polyhedra
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3659288 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Maximum matching of given weight in complete and complete bipartite graphs
• On certain polytopes associated with graphs
• On the Assignment Polytope
• Some NP-complete problems in linear programming
• The adjacency relation on the traveling salesman polytope is NP-Complete

Cited in

(8)

• On affine reducibility of combinatorial polytopes
• The common face of some 0/1-polytopes with NP-complete nonadjacency relation
• Critical edges for the assignment problem: complexity and exact resolution
• A criterion for the adjacency of vertices of polytopes generated by subsets of symmetric groups
• A full description of polytopes related to the index of the lowest nonzero row of an assignment matrix
• Shortest reconfiguration of perfect matchings via alternating cycles
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
• Vertex adjacencies in the set covering polyhedron

This page was built for publication: Adjacency on the constrained assignment problem

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