Group Seminar
"Algorithms and Complexity"
Winter Term 2011/12
Alexander Souza
24.11.2011, 13:30, SR 052-02-017
PTAS for Densest k-Subgraph in Interval Graphs
Dr. Tim Nonner, IBM ResearchGiven an interval graph and integer k, we consider the problem of finding a subgraph of size k with a maximum number of induced edges, called densest k subgraph problem in interval graphs. It has been shown that this problem is NP hard even for chordal graphs (Perl,Corneil'84), and there is probably no PTAS for general graphs (Khot'06). However, the exact complexity status for interval graphs is a long-standing open problem (Perl,Corneil'84), and the best known approximation result is a 3-approximation algorithm (Liazi,Milis08}. We shed light on the approximation complexity of finding a densest k-subgraph in interval graphs by presenting a polynomial-time approximation scheme (PTAS), that is, we show that there is an (1+epsilon)-approximation algorithm for any epsilon > 0, which is the first such approximation scheme for the densest k subgraph problem in an important graph class without any further restrictions.
24.11.2011, 14:00, SR 052-02-017
Local Matching Dynamics in Social Networks
Jun.-Prof. Dr. Martin Hoefer, RWTH AachenStable marriage and roommates problems have many applications in economics and computer science. In these scenarios, each player is a rational agent and wants to be matched to another player. Players have preferences over their possible matches. In many applications, however, a player is not aware of all other players and must explore the population before finding a good match. We incorporate this aspect by studying stable matching under dynamic locality constraints in social networks. Our interest is to characterize the behavior of local improvement dynamics and their convergence to locally stable matchings that do not allow any incentive to deviate with respect to their imposed information structure in the network.
24.11.2011, 15:00, SR 052-02-017
The Car Sharing Problem
Jun.-Prof. Dr. Patrick Briest, U PaderbornWe consider a novel type of metric task system, termed the car sharing problem, in which the operator of a car sharing program aims to serve the requests of customers occurring at different locations. Requests are modeled as a stochastic process with known parameters and a request is served if a car is located at the position of its occurrence at this time. Customers pay the service provider according to the distance they travel and similarly the service provider incurs cost proportional to the distance traveled when relocating a car from one position to another between requests. We derive an efficient algorithm to compute a redistribution policy that yields average long-term revenue within a factor of 2 of optimal and provide a complementing proof of APX-hardness. Considering a variation of the problem in which requests occur simultaneously in all locations, we arrive at an interesting repeated balls-into-bins process, for which we prove bounds on the average number of occupied bins.