Contributed Session Mon.1.H 3012

Monday, 10:30 - 12:00 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

Matching

 

Chair: Sigrid Knust

 

 

Monday, 10:30 - 10:55 h, Room: H 3012, Talk 1

Sigrid Knust
Scheduling sports tournaments on a single court based on special 2-factorizations

 

Abstract:
We consider a sports tournament for an odd number of teams where every team plays exactly two matches in each round and all matches have to be scheduled consecutively on a single court. We construct schedules for any number
of teams minimizing waiting times by using special 2-factorizations of the complete graph (Hamiltonian 2-factorization, solutions to special cases of the Oberwolfach problem).

 

 

Monday, 11:00 - 11:25 h, Room: H 3012, Talk 2

Mizuyo Takamatsu
Matching problems with delta-matroid constraints

Coauthor: Naonori Kakimura

 

Abstract:
Given an undirected graph G=(V,E) and a directed graph D=(V,A), the master/slave matching problem is to find a matching of maximum cardinality in G such that for each arc (u,v) in A with u being matched, v is also matched. This problem is known to be NP-hard, but polynomially solvable in a special case where the maximum size of a connected component of D is at most two.
As a generalization of the above polynomially solvable problem, we introduce a class of the delta-matroid matching problem. In this problem, given an undirected graph G=(V,E) and a projection of a linear delta-matroid (V,F), we find a maximum cardinality matching M such that the set of the end vertices of M belongs to F. We first show that it can be solved in polynomial time if the delta-matroid is generic, which enlarges a polynomially solvable class of constrained matching problems. In addition, we design a polynomial-time algorithm when the graph is bipartite and the delta-matroid is defined on one vertex side. This result is extended to the case where a linear matroid constraint is additionally imposed on the other vertex side.

 

 

Monday, 11:30 - 11:55 h, Room: H 3012, Talk 3

Michael Kapralov
On the communication and streaming complexity of maximum bipartite matching

Coauthors: Ashish Goel, Sanjeev Khanna

 

Abstract:
Consider the following communication problem. Alice and Bob are given a bipartite graph G with 2n nodes whose edges are partitioned adversarially into two sets. Alice holds the first set, and Bob holds the second set. Alice sends Bob a message that depends only on her part of the graph, after which Bob must output a matching in G. What is the minimum size of the message that allows Bob to recover a matching of size at least (1-ε) times the maximum matching in G, as a function of n? The minimum message size is the one-round communication complexity of approximating bipartite matching, which is also a lower bound on the space needed by a one-pass streaming algorithm to obtain a (1-ε)-approximation. In this talk we are interested in the best approximation one can obtain with linear communication and space. Prior to our work, only the trivial 1/2 approximation was known.
We show that Alice and Bob can achieve a 2/3-approximation with a message of linear size, and then build on our techniques to design a deterministic streaming 1-1/e approximation in a single pass for the case of vertex arrivals. Finally, we show that both results are best possible.

 

  Payday Loans In North Carolina. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.