Matroid and knapsack house allocation

DOI10.1016/J.IC.2026.105459MaRDI QIDQ7262283zbMATH OpenFDO

Authors Jinshan Zhang, Piotr Krysta

Publication date 11 June 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2026.105459

zbMATH Keywords

algorithmic mechanism designapproximation algorithmsindifference or tiematching under preferencesmatroid and knapsack constraints

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A new solution to the random assignment problem.
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• AdWords and generalized online matching
• An approximation algorithm for the generalized assignment problem
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• Budget feasible mechanisms on matroids
• College Admissions and the Stability of Marriage
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Consistency in house allocation problems
• Deferred acceptance algorithms: history, theory, practice, and open questions
• Efficiency of truthful and symmetric mechanisms in one-sided matching
• Envy-free allocations respecting social networks
• Envy-free matchings with one-sided preferences and matroid constraints
• Faster matroid intersection
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Matroids, secretary problems, and online mechanisms
• On the complexity of fair house allocation
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online vertex-weighted bipartite matching and single-bid budgeted allocations
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Randomized primal-dual analysis of RANKING for online bipartite matching
• Ranking on arbitrary graphs: rematch via continuous LP with monotone and boundary condition constraints
• Size versus fairness in the assignment problem
• Size versus truncation robustness in the assignment problem
• Size versus truthfulness in the house allocation problem
• Social welfare in one-sided matchings: random priority and beyond
• Truthful generalized assignments via stable matching
• Two algorithms for the student-project allocation problem
• Welfare maximization and truthfulness in mechanism design with ordinal preferences

This page was built for publication: Matroid and knapsack house allocation

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