id: 06101796
dt: a
an: 06101796
au: Mastrolilli, Monaldo; Stamoulis, Georgios
ti: Constrained matching problems in bipartite graphs.
so: Mahjoub, A. Ridha (ed.) et al., Combinatorial optimization. Second
    international symposium, ISCO 2012, Athens, Greece, April 19-21, 2012.
    Revised selected papers. Berlin: Springer (ISBN 978-3-642-32146-7/pbk).
    Lecture Notes in Computer Science 7422, 344-355 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-32147-4_31
ab: Summary: We study the following generalization of maximum matchings in
    bipartite graphs: given a bipartite graph such that each edge has a
    unique color $c _{j }$, we are asked to find a maximum matching that
    has no more than $w _{j }$ edges of color $c _{j }$. We study
    bi-criteria approximation algorithms for this problem based on linear
    programming techniques and we show how we can obtain a family of
    algorithms with varying performance guarantees that can violate the
    color bounds. Our problem is motivated from network problems in optical
    fiber technologies.
rv: