Zobrazeno 1 - 7
of 7
pro vyhledávání: '"Leichter, Marilena"'
We show that there exist $k$-colorable matroids that are not $(b,c)$-decomposable when $b$ and $c$ are constants. A matroid is $(b,c)$-decomposable, if its ground set of elements can be partitioned into sets $X_1, X_2, \ldots, X_l$ with the following
Externí odkaz:
http://arxiv.org/abs/2206.12896
Our main contribution is a polynomial-time algorithm to reduce a $k$-colorable gammoid to a $(2k-2)$-colorable partition matroid. It is known that there are gammoids that can not be reduced to any $(2k-3)$-colorable partition matroid, so this result
Externí odkaz:
http://arxiv.org/abs/2107.03795
We revisit the fully online matching model (Huang et al., J.\ ACM, 2020), an extension of the classic online matching model due to Karp, Vazirani, and Vazirani (STOC 1990), which has recently received a lot of attention (Huang et al., SODA 2019 and F
Externí odkaz:
http://arxiv.org/abs/2102.09432
It is an easy observation that a natural greedy approach yields a $\left(d-O(1)\right)$-factor approximation algorithm for the maximum induced matching problem in $d$-regular graphs. The only considerable and non-trivial improvement of this approxima
Externí odkaz:
http://arxiv.org/abs/1708.02028
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Leichter, Marilena Susan
We study combinatorial optimization problems related to covering and scheduling problems, such as the Minimum Hitting Set of Bundles problem, the Generalized Min Sum Set Cover problem, problems related to Matroid Intersection Covers, and the Bipartit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od_______518::0ab12ccedc0d9afd7d0fe484301bd5e0
https://mediatum.ub.tum.de/1602044
https://mediatum.ub.tum.de/1602044
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.