Fast primal-dual update against local weight update in linear assignment problem and its application

DOI10.1016/j.ipl.2023.106432zbMath1529.90082arXiv2208.11325MaRDI QIDQ6072219

Shinya Shiroshita, Yu Yokoi, Kohei Morita, Yutaro Yamaguchi

Publication date: 12 October 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.11325

zbMATH Keywords

design of algorithmsassignment problem (bipartite matching)envy-free allocation of indivisible items (EF1/EFX)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Solving the Assignment Problem by Relaxation
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The alternating basis algorithm for assignment problems
• The State of the Art in Dynamic Graph Algorithms
• On some techniques useful for solution of transportation network problems
• A framework for dynamic matching in weighted graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast primal-dual update against local weight update in linear assignment problem and its application