Approximation by lexicographically maximal solutions in matching and matroid intersection problems

DOI10.1016/J.TCS.2022.01.035OpenAlexW3186337117MaRDI QIDQ2118859FDOQ2118859

Authors Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi

Publication date 23 March 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

matchingmatroid intersectionapproximation ratiolexicographical maximality

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Matroid matching: the power of local search
• Matroid matching: the power of local search
• Exact and approximation algorithms for weighted matroid intersection
• A Fast Approximation for Maximum Weight Matroid Intersection
• Exact and approximation algorithms for weighted matroid intersection

Cites work

• scientific article; zbMATH DE number 3544074 (Why is no real title available?)
• An Analysis of the Greedy Heuristic for Independence Systems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Exact and approximation algorithms for weighted matroid intersection
• MATROID INTERSECTION WITH PRIORITY CONSTRAINTS
• Matroid intersection algorithms
• Rank-maximal matchings
• Reducing rank-maximal to maximum weight matching

Cited in

(3)

• scientific article; zbMATH DE number 26304 (Why is no real title available?)
• Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems
• Minimum transversals of maximum matchings as approximate solutions to the bisection problem

This page was built for publication: Approximation by lexicographically maximal solutions in matching and matroid intersection problems

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