Matching: A Well-Solved Class of Integer Linear Programs

Jack Edmonds, Ellis L. Johnson

Type: Book-Chapter

Publication Date: 2003-01-01

Citations: 93

DOI: https://doi.org/10.1007/3-540-36478-1_3

View Publication

Download PDF

Locations

Lecture notes in computer science - View
CiteSeer X (The Pennsylvania State University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Matching: A Well-Solved Class of Integer Linear Programs.	2001	Jack Edmonds Ellis L. Johnson
+	Matching, a well solved class of integer linear programs	1970	Jennifer Edmonds
+ PDF Chat	A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem	2022	Étienne Bamas Marina Drygala Ola Svensson
+ PDF Chat	A Unified Framework for Integer Programming Formulation of Graph Matching Problems	2015	Bahram Alidaee Haibo Wang Hugh Sloan
+	Matching Theory	2012	Masoud Barah Ehsan Mazaheri
+ PDF Chat	A Unified Framework for Integer Programming Formulation of Graph Matching Problems	2024	Bahram Alidaee Haibo Wang Hugh Sloan
+	The Feasible Matching Problem	2012	Yuejian Peng Papa A. Sissokho
+ PDF Chat	Approximation by lexicographically maximal solutions in matching and matroid intersection problems	2022	Kristóf Bérczi Tamás Király Yutaro Yamaguchi Yu Yokoi
+	Solving matching problems using Karmarkar’s algorithm	1990	John E. Mitchell Mike Todd
+	An optimal matching problem with constraints	2018	José M. Mazón Julio D. Rossi J. Toledo
+ PDF Chat	Integer Linear Programming	1986	H. T. Lau
+	An algorithm for linear programming that is easy to implement	1989	J.C. Culioli V. Protopopescu
+	A Polynomial Time Algorithm for a Special Case of Linear Integer Programming	2011	Golnaz Ghasemiesfeh Hanieh Mirzaei Yahya Tabesh
+	A New Procedure for Solving Integer Linear Programming Problems	2014	S.F. Tantawy
+	Integer Linear Programming Problem	1964	Eizo Abe
+	Mixed Integer Linear Programming – A Working Algorithm	1971	T.G. O’Flaherty
+ PDF Chat	Revisiting a Cutting-Plane Method for Perfect Matchings	2020	Amber Q Chen Kevin K. H. Cheung P. Michael Kielstra Avery D. Winn
+	A Short Introduction to Integer Linear Programming	2014
+	On a matching problem	1952	Chikio Hayashi Hirotugu Akaike
+	Efficient algorithms for special classes of linear programming problems	1989	誉人久野

Works That Cite This (17)

Action	Title	Year	Authors
+	Mixed-Integer Vertex Covers on Bipartite Graphs	2007	Michele Conforti Bert Gerards Giacomo Zambelli
+ PDF Chat	Optimization with binet matrices	2006	Gautam Appa Balázs Kotnyek Konstantinos Papalamprou Leonidas Pitsoulis
+ PDF Chat	Gain-line graphs via G-phases and group representations	2020	Matteo Cavaleri Daniele D’Angeli Alfredo Donno
+	Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method	2010	Edward D. Kim
+ PDF Chat	A Strongly Polynomial-Time Algorithm forWeighted General Factors with Three Feasible Degrees*	2024	Shuai Shao Stanislav Živný
+ PDF Chat	Total graph of a signed graph	2022	Francesco Belardo Zoran Stanić Tomas Zaslavsky
+ PDF Chat	A Randomized Rounding Approach to the Traveling Salesman Problem	2011	Shayan Oveis Gharan Amin Saberi Mohit Singh
+	Improving Christofides' Algorithm for the s-t Path TSP	2011	Hyung-Chan An Robert Kleinberg David B. Shmoys
+ PDF Chat	Approximability of Bounded Occurrence Max Ones	2006	Fredrik Kuivinen
+	Free multiflows in bidirected and skew-symmetric graphs	2007	Maxim A. Babenko Alexander V. Karzanov

Works Cited by This (2)

Action	Title	Year	Authors
+	C. Berge, Théorie des graphes et ses applications. VIII + 277 S. m. 117 Abb. Paris 1958. Dunod Editeur. Preis geb. 3400 F	1960	L. Bittner
+	Maximum matching and a polyhedron with 0,1-vertices	1965	Jack Edmonds