NDLI: Matroid Secretary for Regular and Decomposable Matroids

Please wait, while we are loading the content...

Matroid Secretary for Regular and Decomposable Matroids

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kortsarz, Guy Dinitz, Michael
Copyright Year	2014
Abstract	In the matroid secretary problem we are given a stream of elements in random order and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the stream, then we can never get rid of it, and if we choose not to accept it, then we cannot later add it. Babaioff, Immorlica, and Kleinberg [Proceedings of SODA'07] introduced this problem, gave O(1)-competitive algorithms for certain classes of matroids, and conjectured that every matroid admits an O(1)-competitive algorithm. However, most matroids that are known to admit an O(1)-competitive algorithm can be easily represented using graphs (e.g., graphic, cographic, and transversal matroids). In particular, there is very little known about $F$-representable matroids (the class of matroids that can be represented as elements of a vector space over a field $F$), which are one of the foundational types of matroids. Moreover, most of the known techniques are as dependent on graph theory as they are on matroid theory. We go beyond graphs by giving O(1)-competitive algorithms for regular matroids (the class of matroids that are representable over any field) and use techniques that are fundamentally matroid-theoretic rather than graph-theoretic. Our main technique is to leverage the seminal regular matroid decomposition theorem of Seymour, which gives a method for decomposing any regular matroid into matroids which are graphic, cographic, or isomorphic to a simple 10-element matroid. We show how to combine in a black-box manner any algorithms for these basic classes into an algorithm for a given regular matroid, i.e., how to respect the decomposition. In fact, this allows us to generalize beyond regular matroids to any class of matroids that admits such a decomposition into classes for which we already have good algorithms. In particular, we give an O(1)-competitive algorithm for the class of max-flow min-cut matroids, which Seymour showed can be decomposed into regular matroids and copies of the Fano matroid.
Starting Page	1807
Ending Page	1830
Page Count	24
File Format	PDF
ISSN	00975397
DOI	10.1137/13094030X
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	5
Volume Number	43
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2014-10-21
Access Restriction	Subscribed
Subject Keyword	Online algorithms Matroids, geometric lattices matroid secretary regular matroids General online algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Matroid Secretary Problem in the Random-Assignment Model

Matroid Secretary for Regular and Decomposable Matroids

Matroid secretary for regular and decomposable matroids.

Matroid Secretary for Regular and Decomposable Matroids

Matroid secretary for regular and decomposable matroids (2013)

The matroid secretary problem for minor-closed classes and random matroids

Matroid secretary for regular and decomposable matroids (2013)

Improved Bounds for Matroid Partition and Intersection Algorithms

Algebraic Algorithms for Matching and Matroid Problems

Matroid Secretary for Regular and Decomposable Matroids

Similar Documents

Matroid Secretary Problem in the Random-Assignment Model

Matroid Secretary for Regular and Decomposable Matroids

Matroid secretary for regular and decomposable matroids.

Matroid Secretary for Regular and Decomposable Matroids

Matroid secretary for regular and decomposable matroids (2013)

The matroid secretary problem for minor-closed classes and random matroids

Matroid secretary for regular and decomposable matroids (2013)

Improved Bounds for Matroid Partition and Intersection Algorithms

Algebraic Algorithms for Matching and Matroid Problems

Matroid Secretary for Regular and Decomposable Matroids