Simultaneous eating algorithm and greedy algorithm in assignment problems

DOI10.1007/S10878-023-01063-0MaRDI QIDQ6176397zbMATH OpenOpenAlexFDO

Authors Ping Zhan

Publication date 22 August 2023

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10878-023-01063-0

zbMATH Keywords

ordinal efficiencyordinal preferencepolymatroidsubmodular function optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Individual preferences (91B08) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Recommendations

• Simultaneous approximation by greedy algorithms
• A class of greedy algorithms for the generalized assignment problem
• Some recent results in the analysis of greedy algorithms for assignment problems
• Heuristic and exact algorithms for the simultaneous assignment problem
• Greedy solutions of selection and ordering problems
• Greedy in Approximation Algorithms
• On the Greedy Solution of Ordering Problems
• An algorithm for the assignment problem
• scientific article; zbMATH DE number 1146090
• A comparison of two algorithms for the assignment problem

Cites work

• A constructive proof of the ordinal efficiency welfare theorem
• A new solution to the random assignment problem.
• A simple characterization of assignment mechanisms on set constraints
• A solution to the random assignment problem on the full preference domain
• Constrained random matching
• Convex Analysis
• Efficient rules for probabilistic assignment
• Extended random assignment mechanisms on a family of good sets
• How to divide when there isn't enough. From Aristotle, the Talmud, and Maimonides to the axiomatics of resource allocation
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Ordinal efficiency and dominated sets of assignments.
• Ordinal efficiency and the polyhedral separating hyperplane theorem
• Submodular functions and optimization.
• Submodular optimization views on the random assignment problem
• Sufficient conditions for the optimality of the greedy algorithm in greedoids
• The vigilant eating rule: a general approach for probabilistic economic design with constraints
• Two axiomatic approaches to the probabilistic serial mechanism

Cited in

(1)

• Ex ante and ex post envy-freeness on polytope resources

This page was built for publication: Simultaneous eating algorithm and greedy algorithm in assignment problems

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