The popular matching and condensation problems under matroid constraints

DOI10.1007/S10878-015-9965-8MaRDI QIDQ346527zbMATH OpenOpenAlexFDO

Authors Naoyuki Kamiyama

Publication date 29 November 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-015-9965-8

zbMATH Keywords

matroidpopular condensationpopular matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Recommendations

• The popular matching and condensation problems under matroid constraints
• Popular matchings with ties and matroid constraints
• Popular matchings with two-sided preference lists and matroid constraints
• A characterization of weighted popular matchings under matroid constraints
• An optimal algorithm for the popular condensation problem

Cites work

• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Fixed-Point Approach to Stable Matchings and Some Applications
• A Two-Sided Discrete-Concave Market with Possibly Bounded Side Payments: An Approach by Discrete Convex Analysis
• A matroid approach to stable matchings with lower quotas
• A weighted matroid intersection algorithm
• An optimal algorithm for the popular condensation problem
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Matching Theory for Combinatorial Geometries
• Matroid intersection algorithms
• Optimal popular matchings
• Popular Matchings
• Popular Matchings in the Capacitated House Allocation Problem
• Popular matchings in the weighted capacitated house allocation problem
• Popular matchings with variable item copies
• Popular matchings: structure and algorithms
• The college admissions problem with lower and common quotas
• The generalized popular condensation problem
• Weighted popular matchings

Cited in

(8)

• The generalized popular condensation problem
• A polyhedral approach for a constrained matching problem
• A characterization of weighted popular matchings under matroid constraints
• Solving the maximum popular matching problem with matroid constraints
• Pareto stable matchings under one-sided matroid constraints
• The popular matching and condensation problems under matroid constraints
• Popular matchings with ties and matroid constraints
• Popular matchings with two-sided preference lists and matroid constraints

This page was built for publication: The popular matching and condensation problems under matroid constraints

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