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.

 

  The best way to go for you to know the credible Michigan Loans Online providers. But at the same time, it acts only with sexual arousal. Buy Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.