Improved Online Algorithms for Secretary Problems on Graphs and Hypergraphs

Speaker

Andreas Tönnes (Informatik 1)
Title Improved Online Algorithms for Secretary Problems
on Graphs and Hypergraphs
When 15.05.2013, 10:00
Where Room 5052
Abstract We study online variants of weighted bipartite matching on graphs and hypergraphs. In our model for online matching, the vertices on the right-hand side of a bipartite graph are given in advance and the vertices on the left-hand side arrive online in random order. Whenever a vertex arrives, its adjacent edges with the corresponding weights are revealed and the online algorithm has to decide which of these edges should be included in the matching. The studied matching problems have applications, e.g., in online ad auctions and combinatorial auctions. In an auction, the right-hand side vertices correspond to items and the left-hand side vertices to bidders.

We present a new algorithmic approach that yields improved competitive ratios for weighted matching on graphs and hypergraphs. On graphs, we can improve the competitive ratio from 8 to 1/(1−ln(2)) = 3.26. On hypergraphs with (d+1)-uniform hyperedges, corresponding to combinatorial auctions with bundles of size d, we achieve competitive ratio O(d) in comparison to the previously known ratios O(d^2) and O(d log n).

In this talk I will present heap abstraction based on hyperedge replacement grammars, focusing on necessary grammar properties and how to establish them. Then we will discuss the transfer of the obtained results in the related field of separation logic as well as for performing interprocedural analysis.