Source-linked AI summary
Algorithms for Secretary Problems on Graphs and Hypergraphs
Nitish Korula, Martin Pal
TL;DR
The paper studies online matching and related secretary problems where decisions must be made as arrivals are revealed, motivated partly by advertising reservation systems. It develops improved competitive algorithms, including an 8-competitive bipartite matching algorithm and a 2e-competitive graphic-matroid algorithm, while extending the framework to hypergraphs and groups.
Problem
Online secretary-type matching problems require real-time decisions under random arrivals, including weighted slot assignment, hypergraph edge selection, and graphic-matroid independence.
Method
The paper analyzes sampling, greedy matching, and pruning approaches for online weighted matching, extending them to hypergraphs, groups, and graphic matroids.
Results
An 8-competitive algorithm improves the previous ratio of 16 for the more general bipartite vertex-at-a-time matching problem, while a graphic-matroid algorithm is 2e-competitive.
Takeaways & Limitations
The analysis yields competitive algorithms beyond bipartite matching, including disjoint hypergraph edge sets and maximum-weight acyclic subgraphs.
Takeaways & Limitations
The paper does not provide tighter analysis for the hypergraph vertex-at-a-time problem or optimize the stated constants, and the groups variant remains open for constant competitiveness.
Abstract
from arXiv · showhide
We examine several online matching problems, with applications to Internet advertising reservation systems. Consider an edge-weighted bipartite graph G, with partite sets L, R. We develop an 8-competitive algorithm for the following secretary problem: Initially given R, and the size of L, the algorithm receives the vertices of L sequentially, in a random order. When a vertex l \in L is seen, all edges incident to l are revealed, together with their weights. The algorithm must immediately either match l to an available vertex of R, or decide that l will remain unmatched. Dimitrov and Plaxton show a 16-competitive algorithm for the transversal matroid secretary problem, which is the special case with weights on vertices, not edges. (Equivalently, one may assume that for each l \in L, the weights on all edges incident to l are identical.) We use a similar algorithm, but simplify and improve the analysis to obtain a better competitive ratio for the more general problem. Perhaps of more interest is the fact that our analysis is easily extended to obtain competitive algorithms for similar problems, such as to find disjoint sets of edges in hypergraphs where edges arrive online. We also introduce secretary problems with adversarially chosen groups. Finally, we give a 2e-competitive algorithm for the secretary problem on graphic matroids, where, with edges appearing online, the goal is to find a maximum-weight acyclic subgraph of a given graph.
1 Introduction
The paper studies secretary-type problems for online maximum-weight independent sets, motivated by real-time advertising reservations. It develops improved and extended algorithms for bipartite matching, hypergraphs, adversarially grouped arrivals, and graphic matroids.
- Problem setting: Online optimization requires irrevocable accept-or-reject decisions before future elements and weights are known.Competitive analysis compares the online algorithm with an optimal offline solution.
- Secretary model: Random arrival order underlies secretary-type problems for selecting maximum-weight independent sets.The classical secretary algorithm finds the maximum-weight element with probability 1/e.
- Motivation and model: The paper models advertising reservations as edge-weighted bipartite matching, with arriving ads revealing weighted slot options and requiring immediate placement decisions.The seller initially knows the slots and seeks to maximize revenue.
- Results and outline: The bipartite vertex-at-a-time matching problem improves the transversal-matroid ratio from 16 to 8, including the more general edge-weighted setting.The transversal-matroid case has equal weights on all edges incident to each arriving left vertex.
- Extensions: The analysis extends to constant-competitive algorithms for hypergraphs with constant edge-size and introduces secretary problems with adversarially chosen groups.Groups arrive in random order after an adversary constructs them.
- Results and outline: A simple 2e-competitive algorithm is obtained for maximum-weight acyclic subgraphs in graphic matroids.Edges appear online, and the selected set must remain acyclic.
2 The Bipartite Vertex-at-a-time Matching Problem
The section analyzes a sample-and-price algorithm for online edge-weighted bipartite matching. A simulation, pruning argument, and random-prefix implementation establish an expected competitive ratio of 8.
- Problem and algorithm: The BVM algorithm sees left vertices in random order and must immediately match each arriving vertex to an available right vertex or leave it unmatched.All incident edges and their weights are revealed upon arrival.
- Offline benchmark: GREEDY is a 2-approximation for offline edge-weighted bipartite matching.For an optimum matching of weight OPT, the greedy matching has weight at least OPT/2.
- Simulation: SIMULATE partitions candidate edges into M1 and M2 using coin flips, then prunes M2 to obtain a matching M3.M1 is already a matching, whereas M2 may contain multiple edges incident to one right vertex.
- Analysis: E[w(M1)] ≥ pOPT/2, while E[w(M2)] ≥ (1−p)OPT/2.The first bound follows by applying GREEDY to the randomly sampled left vertices.
- Online implementation: The final SAMPLEANDPRICE algorithm samples a random prefix, sets right-vertex prices from a greedy matching, and accepts later edges meeting their prices while preserving matching feasibility.Its random-prefix implementation is equivalent to SAMPLEANDPERMUTE.
- Competitive ratio: The final expected bound is E[w(M)] ≥ p(1−p)OPT/2; choosing p = 1/2 yields an expected competitive ratio of 8.The analysis relates the online matching to the tighter pruning argument for SAMPLEANDPERMUTE.
3 Independent Edge Sets in Hypergraphs
The paper extends online secretary-style matching to hypergraphs, introducing HVM and using it to obtain an O(d^2)-competitive algorithm for HEM. The analysis combines randomized simulation, greedy pricing, and component-based charging.
- Problem: HEM selects a maximum-weight set of disjoint hyperedges arriving in random order, with d denoting the maximum hyperedge size.The offline problem is NP-complete for arbitrary hypergraphs, while size-2 edges reduce to online matching in graphs.
- Problem: HVM reveals vertices of L online and requires immediate acceptance or rejection of an incident edge containing one arriving vertex and vertices from R.HEM reduces to HVM by adding one new L-vertex for each original hyperedge.
- Algorithmic setup: GREEDY returns a (d + 1)-approximation for the maximum-weight disjoint edge set under the (d + 1)-uniform HVM assumption.Each edge contains one vertex of L and d vertices of R.
- Analysis: The randomized SIMULATE procedure partitions candidate edges into M1 and M2, then constructs M3 from suitable edges of M2.The procedure processes edges in decreasing weight order, assigns each L-vertex once, and flips a coin with probability p to choose M1 versus M2.
- Analysis: For the first two sets, E[w(M1)] ≥ p · OPT/(d + 1) and E[w(M2)] ≥ (1 − p)OPT/(d + 1).These bounds support the later analysis of M3.
- Analysis: 3 is the bound on the expected size of each auxiliary-tree subtree, yielding an expectation ratio of at most 6 between Revenue2 and Revenue3.The analysis charges each connected component to its heaviest edge and uses an auxiliary directed forest.
- Final result: SAMPLEANDPRICE is an O(d^2)-competitive algorithm for the HVM secretary problem and therefore supplies the stated HEM approach.It samples an initial prefix to set prices, then accepts high-weight edges meeting those prices when they are disjoint from the current matching.
- Scope: The extended abstract does not provide a tighter HVM analysis or optimize the constants, although d = 2 yields a constant competitive ratio for online non-bipartite matching.The authors explicitly leave tighter analysis and constant optimization open in this presentation.
4 Secretary Problems with Groups
The section studies secretary problems where an adversary groups elements before groups arrive in random order, focusing on bipartite matching with grouped vertices or edges. It proves an O(log n)-competitive algorithm for grouped BVM, while presenting a constant-competitiveness conjecture for a specialized algorithm.
- Problem model: Adversarially formed groups arrive in random order, with all elements of each group revealed simultaneously.The groups are fixed before arrival, and the algorithm receives the number of groups rather than the number of elements.
- Applications: Grouped secretary problems arise in advertising because advertisers may submit multiple ads and ad-slot bids, so random advertiser order does not randomize individual ads.The groups correspond to ads submitted by a given advertiser.
- BVM with groups: O(log n)-competitive performance is obtained for BVM with groups.The algorithm samples the first half, selects a random threshold scale, and greedily matches above that threshold in the second half.
- BVM with groups: Grouped matching can defeat the natural Sample-And-Price strategy because group-level assignments need not match the assignments obtained when a group is sampled.This breaks the correspondence that supports the basic BVM analysis.
- BVM with groups: For the proposed sampling construction, p = 1/2 makes the expected weight of M2 equal to that of M1 and equalizes expected right-vertex degrees.This equality does not by itself establish a constant-factor lower bound for M3.
- BVM with groups: SAMPLEWITHGROUPS is conjectured to be constant-competitive for BVM with groups.Its analysis uses sampled groups, a greedy matching, and deletion of conflicting edges from the constructed matching.
5 Graphic Matroids
The section gives a reduction from the graphic matroid secretary problem to classical secretary problems by orienting the graph in one of two directions. This yields a 2e-competitive algorithm for selecting a maximum-weight acyclic edge set.
- Problem: The graphic matroid secretary problem selects a maximum-weight acyclic edge subset when graph edges arrive in random order.Accepted edges must be chosen irrevocably upon arrival.
- Algorithm: The algorithm randomly chooses one of two acyclic orientations and runs an independent secretary algorithm for each vertex’s outgoing edges.The union of accepted edges remains acyclic because each vertex has at most one outgoing edge in the chosen orientation.
- Analysis: Each vertex-level secretary algorithm recovers at least a 1/e fraction of its heaviest outgoing edge in expectation.The analysis compares the resulting union with a maximum-weight acyclic subgraph.
- Result: 2e-competitive performance is achieved for the graphic matroid secretary problem.This improves the previously stated 16-competitive guarantee for the same secretary problem.
6 Conclusions and Open Problems
The paper identifies unresolved questions about groups, lower bounds, greedy matching losses, and general matroid secretary algorithms.
- Constant-competitive algorithms for the BVM problem with groups remain an open possibility.
- Few lower bounds are known beyond 1/e for the original secretary problem.The paper notes that stronger lower bounds may require new techniques.
- Greedy matching construction loses a factor of 2 in the basic BVM problem.The paper asks whether pricing with an optimal matching on sampled vertices could yield a 4-competitive or even O(1)-competitive algorithm.
- An O(1)-competitive algorithm for the general matroid secretary problem remains open.Important special cases, including transversal and graphic matroids, have already reached small constant competitive ratios.
A.1 Proof of Lemma 2.5
The proof establishes that SAMPLEANDPRICE is 8-competitive by comparing revenues in two matchings through per-vertex degree-conditioned bounds and a worst-case ratio argument.
- SAMPLEANDPRICE is 8-competitive for the BVM problem.
- Revenue2(v) is the total weight of M2 edges incident to v, while Revenue3(v) is the weight of its at-most-one M3 edge.
- The proof bounds E[Revenue3(v)] in terms of E[Revenue2(v)] using degree probabilities Pi and conditional revenues wi.It establishes Pi ≤ (1−p)Pi−1 and wi ≤ i/(i−1)wi−1.
- The worst-case ratio occurs when the probability and conditional-revenue constraints hold with equality.If a constraint is slack, adjusting the corresponding variables increases the ratio, contradicting optimality.
- The analysis allows a possible final vertex with only one additional incident edge by treating the case as helping the analysis or adding zero-weight edges.
- E[w(M3)] ≥ p(1−p)OPT/2 completes the proof of Lemma 2.5.
A.2 Other Proofs
The other proofs establish an O(log n) guarantee for BVM with groups and develop structural arguments for matching and graphic-matroid analyses.
- The BVM-with-groups algorithm samples half the vertices, chooses a random logarithmic threshold level, and greedily builds a matching above that threshold.
- The proof reduces the weight analysis to showing E[mi(M)] ≥ ni(OPT)/O(log n) for each relevant weight level.
- For higher weight levels, the analysis separates cases according to whether most sufficiently heavy optimal edges lie outside or inside the heaviest edge’s group.
- When heavy optimal edges lie outside the heaviest edge’s group, threshold selection and random ordering yield a matching of expected size at least i/4 before logarithmic averaging.
- When heavy optimal edges concentrate in the heaviest edge’s group, the proof again obtains a matching of expected size at least i/4 under a suitable threshold choice.
- The graphic-matroid analysis charges each edge of an optimal forest to the heavier endpoint incident edge, with each vertex charged at most once.