Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems

DOI10.1016/J.TCS.2022.01.035arXiv2107.09897MaRDI QIDQ6373379FDOQ6373379

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

Publication date: 21 July 2021

Abstract: We study how good a lexicographically maximal solution is in the weighted matching and matroid intersection problems. A solution is lexicographically maximal if it takes as many heaviest elements as possible, and subject to this, it takes as many second heaviest elements as possible, and so on. If the distinct weight values are sufficiently dispersed, e.g., the minimum ratio of two distinct weight values is at least the ground set size, then the lexicographical maximality and the usual weighted optimality are equivalent. We show that the threshold of the ratio for this equivalence to hold is exactly $2$. Furthermore, we prove that if the ratio is less than $2$, say $alpha$, then a lexicographically maximal solution achieves $(alpha/2)$-approximation, and this bound is tight.

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

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 Q6373379)