Computer Science – Data Structures and Algorithms
Scientific paper
2008-07-07
Computer Science
Data Structures and Algorithms
15 pages, 2 figures
Scientific paper
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.
Korula Nitish
Pal Martin
No associations
LandOfFree
Algorithms for Secretary Problems on Graphs and Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algorithms for Secretary Problems on Graphs and Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Secretary Problems on Graphs and Hypergraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-268066