A Multiply Constrained Matroid Optimization Problem

Leclerc, Matthias and Rendl, Franz (1989) A Multiply Constrained Matroid Optimization Problem.
Published in: Discrete mathematics Vol. 73 (1-2). pp. 207-212.

Abstract

We consider the problem of finding a minimum weight basis of a matroid satisfying additional conditions which can be described as follows: each element of the matroid is assigned a color and feasible bases can use at most a prescribed number of elements from each color. This problem is a special case of weighted matroid intersection. We provide an algorithm for this problem which improves general matroid intersection algorithms by exploiting the simple structure of the side constraints.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 5 (Google Scholar) | 0 (Web of Science)
Uncontrolled Keywords: matroids minimum cost basis minimum cost schedule minimum spanning tree multi-color matroid optimization problem preprocessing phase
Subjects:
  • 05-XX Combinatorics > 05Bxx Designs and configurations > 05B35 Matroids, geometric lattices

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks

  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B35 Scheduling theory, deterministic

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

    		•
    Divisions: Mathematical Institute
    Related URLs:
    Deposit Information:
    ZAIK Number: zpr87-040
    Depositing User: Archive Admin
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 19 Jan 2012 12:28
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/40