Computer Science – Data Structures and Algorithms

Scientific paper

[
0.00
] – not rated yet
Voters
0
Comments 0

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**

Computer Science – Data Structures and Algorithms

Scientist

**Pal Martin**

Computer Science – Computer Science and Game Theory

Scientist

No associations

LandOfFree

If you have personal experience with

Algorithms for Secretary Problems on Graphs and Hypergraphsdoes not yet have a rating. At this time, there are no reviews or comments for this scientific paper.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

Use Google custom search:

All data on this website is collected from public sources.
Our data reflects the most accurate information available at the time of publication.