Matroid Secretary Problem: Intersection of Matroids & Variants
Variants of the Secretary Problem with matroid constraints have been explored, allowing for hiring multiple secretaries based on certain constraints to maximize total value. The Matroid Secretary Problem, a crucial variant, presents challenges and opportunities for algorithmic solutions in various applications such as auctions. Recent progress has been made towards achieving competitive algorithms for specific matroids, but there is ongoing research to extend beyond matroid constraints and improve competitive guarantees.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Framework for the Secretary Problem on the Intersection of Matroids Moran Feldman Ola Svensson Rico Zenklusen
The (Classical) Secretary Problem n secretaries, each with a unique internal value vi. The Secretaries are interviewed one after the other, in a random order. In the interview: The value of the secretary is revealed. We can hire the secretary, or dismiss her. In both cases, the decision is final. v1v2v3v4v5v6v7v8v9 Goal: Hire the best secretary with high probability. Question: How good can we do? We can succeed with probability 1/e! [Lindley 1961] 2
The Algorithm Algorithm 1. Inspect the first n/e secretaries; let v be the value of the best secretary among these. 2. Interview the rest of the secretaries; hire the first one with value over v. 3
Combinatorial Constraints Many variants of the secretary problem have been considered. One important kind of variants: Allows hiring more than one secretary, as long as the hired secretary obey a constraint. The objective is to maximize the total value of the hired secretaries. Motivated by auction design problems. cardinality knapsack matching 4
M Matroid Secretary Problem What is It? A variant of the above kind with a matroid constraint. Why is it Important? General enough to capture many natural constraints. Structured enough to allow for meaningful results. Allows application in many types of auctions. 5
Examples of Matroid Constraints Cardinality Constraint Partition Matroid Constraint k1 k2 k3 k Matroid Constraint Graphical Matroid Linear Matroid z y x 6
Progress on Matroid Secretary Problem General Problem Introduced with an O(log rank)-competitive algorithm. [BIK07] Improved to O(log1/2 rank) [CL12], and then to O(log log rank) [L14, FSZ15]. Conjectured to have an O(1)-competitive algorithm. Specific Matroids O(1)-competitive algorithms are known for many specific matroids [K05,KP09,KRTV13,DK13]: Cardinality constraint (uniform matroid) Partition matroid Graphic matroid Transversal matroid Regular matroid 7
Beyond Matroids Some non-matroid constraints also got attention [KP09,GHKSV14,BIKK07,MTW13]: What is missing: The guarantee of this general result is quite poor. We want general results beyond matroids with better guarantee (must be less general, to avoid the impossibility). Matching in graphs and hypergraphs Independent sets in graphs Knapsack constraint Intersection of multiple laminar matroids What About More General Results? O(log n)-competitive algorithm for down-monotone set systems. [R16] This is almost tight for so general systems. [BIK07] 8
The Current Work We are interested in the intersection of a constant number of matroid constraints. Basic Message If one has a constant competitive ratio algorithm for every matroid, then one get such an algorithm also for their intersection. Intuitively, if for matroid Mi there is a ci-competitive algorithm, then for the intersection M1 M2 Mk we get a competitive ratio of roughly c1 c2 ... ck 4k2 (assuming some conditions...). 9
More Formally We will survey the proof of this theorem in a minute. The main result is quite complicated. Two implications: Theorem If for matroid Mi there is an order-oblivious ci-OPT-competitive algorithm, then there is a (4k2 c1 c2 .. ck)-competitive algorithm for the intersection M1 M2 Mk. All matroids having known O(1)- competitive algorithms. Theorem Given O(1) partition, laminar, graphic, co-graphic, regular, max- flow min-cut, column-spare linear or transversal matroids and = O(1) other matroids, there is an O(log log rank)-competitive algorithm for the intersection of these matroids. 10
Secondary Result Theorem Given an -competitive algorithm for the intersection of k matroids with a linear objective function, then there is an O( 2k2)-competitive algorithm for the same problem with a submodular objective function. Generalizes a result of [FZ15] which proves the case of a single matroid. The proof follows by combining our technique from the main result with the ideas of [FZ15]. [FZ15] describe many interesting special cases in which its result can be improved, and this is true for our result as well. 11
Outline for the Proof Recall that we have an order-oblivious ci-OPT-competitive algorithm for every matroid Mi. Implies, in particular ci-competitiveness. In a perfect world: OPT(M1 M2 Mk) = OPT(M1) OPT(M2) OPT(Mk) There is a correlation issue, but it can be fixed using the order-obliviousness. ci-OPT-competitive The algorithm for matroid Mi selects every element of OPT(Mi) with probability at least ci. Natural algorithm Run the algorithms for the k matroids in parallel, and select only elements selected by all k algorithms. Every element of OPT(M1 M2 Mk) gets selected with probability at least c1 c2 .. ck. 12
In a Non-perfect World One can easily find a pair of matroids M1 and M2 such that OPT(M1) OPT(M2) = OPT(M1 M2) . Our main technical contribution is an algorithm that eliminates some of the elements. guarantees that, after the elimination, the weight of OPT(M1) OPT(M2) OPT(Mk) is comparable to the weight of the original optimal solution. works online (assuming a random arrival order). So, our algorithm makes the world perfect! (in a sense ) remaining elements elements selected by all of them Our Run the k matroid algorithms in parallel input algorithm 13
Our Technical Algorithm The Greedy Algorithm 1. Let A . 2. While there exists an element u such that A {u} is independent in all k matroids. 3. Add to A the maximum weight element of this kind. 4. Return A Our Algorithm Let Greedy(S) denote the output of the greedy algorithm on a set S. 1. Observe each element with probability (2k 1) / 2k elements, let O be the set of observed elements. 2. Keep an element u arriving after the observation phase if and only if Greedy(O) Greedy(O {u}). The decision about each element can be made online. 14
Some Intuition Alternative View on Our Algorithm Run the greedy algorithm on all elements. Every element that it tries to take is stolen with probability 1 / 2k. Observation 1 The stolen elements have a significant weight because Greedy is a k- approximation algorithm. The stolen elements are the kept elements. Observation 2 A lot of the stolen elements are not spanned by earlier (heavier) stolen elements in any of the matroids. Why? Not spanned by earlier greedy-selected elements Consider an element which will violate this if stolen If not stolen, this element decreases the rank of such elements Spanned by earlier stolen elements 15
