MATROID INTERSECTION WITH PRIORITY CONSTRAINTS MATROID INTERSECTION WITH PRIORITY CONSTRAINTS

Access this Article

Search this Article

Author(s)

Abstract

In this paper, we consider the following variant of the matroid intersection problem. We are given two matroids M_1, M_2 on the same ground set E and a subset A of E. Our goal is to find a common independent set I of M_1, M_2 such that |I∩A| is maximum among all common independent sets of M_1, M_2 and such that (secondly) |I| is maximum among all common independent sets of M_1, M_2 satisfying the first condition. This problem is a matroid-generalization of the simplest case of the rank-maximal matching problem introduced by Irving, Kavitha, Mehlhorn, Michail and Paluch (2006). In this paper, we extend the "combinatorial" algorithm of Irving et at. for the rank-maximal matching problem to our problem by using a Dulmage-Mendelsohn type decomposition for the matroid intersection problem.

Journal

  • Journal of the Operations Research Society of Japan

    Journal of the Operations Research Society of Japan 56(1), 15-25, 2013

    The Operations Research Society of Japan

References:  13

Codes

  • NII Article ID (NAID)
    110009596091
  • NII NACSIS-CAT ID (NCID)
    AA00703935
  • Text Lang
    ENG
  • Article Type
    ART
  • ISSN
    0453-4514
  • NDL Article ID
    024352843
  • NDL Call No.
    Z53-M226
  • Data Source
    CJP  NDL  NII-ELS  IR  J-STAGE 
Page Top