International Workshop on Combinatorial Optimization and Algorithmic Game Theory
Information
- Date:
- Location:
- Registration:
Speakers
- Haris Aziz (UNSW Sydney)
- Kristóf Bérczi (Eötvös Loránd University)
- Endre Boros (Rutgers University)
- Chandra Chekuri (University of Illinois, Urbana-Champaign)
- Naoyuki Kamiyama (Kyushu University)
- Telikepalli Kavitha (Tata Institute of Fundamental Research)
- Yusuke Kobayashi (Kyoto University)
- Euiwoong Lee (New York University)
Program
- January 13
- 10:20--10:30
- 10:30--11:40
- Haris Aziz (UNSW Sydney)
Fair and efficient allocation of indivisible goods and chores
- 11:40--13:30
- 13:30--14:40
- Naoyuki Kamiyama (Kyushu University)
Matching problems under preferences with ties and matroid constraints
- 14:50--16:00
- Kristóf Bérczi (Eötvös Loránd University)
Supermodularity in unweighted graph optimization
- 16:00--16:20
- 16:20--17:30
- Chandra Chekuri (University of Illinois, Urbana-Champaign)
Parallel algorithms for submodular function maximization
- January 14
- 9:30--10:40
- Telikepalli Kavitha (Tata Institute of Fundamental Research)
Popular matchings: Good, bad, and mixed
- 10:50--12:00
- Endre Boros (Rutgers University)
Two-person zero-sum stochastic mean payoff games
- 12:00--14:00
- 14:00--15:10
- Yusuke Kobayashi (Kyoto University)
Restricted 2-matching problems
- 15:10--15:30
- 15:30--16:40
- Euiwoong Lee (New York University)
The number of minimum k-cuts: Improving the Karger-Stein bound
- 16:40--16:50
Title and Abstract
- Haris Aziz (UNSW Sydney)
Fair and efficient allocation of indivisible goods and chores
I consider the problem of fairly and efficiently dividing a set of items.
Much of the fair division literature assumes that the items are ``goods'' i.e.,
they yield positive utility for the agents. There is also some work where the
items are ``chores'' that yield negative utility for the agents. I consider a
more general setting where an agent may have negative or positive utility for
each item. This framework captures, e.g., fair task assignment, where agents
can have both positive and negative utilities for each task. I discuss several
new algorithms for finding fair and efficient allocations in this general
setting. The presentation will be based on a few recent publications.
- Kristóf Bérczi (Eötvös Loránd University)
Supermodularity in unweighted graph optimization
Based on the ellipsoid method, there is a polynomial time
algorithm to compute the optima in the supermodular arc-covering theorem of
Frank and Jordán. In addition, Végh and Benczúr developed a purely
combinatorial
algorithm for the directed node-connectivity augmentation problem, and
their algorithm can be extended to the general supermodular arc-covering
theorem, as well, provided a submodular function minimizing oracle is
available. However, the algorithm of Végh and Benczúr is pretty intricate.
Our goal is to develop simpler algorithms for a wide class of problems, for
example, to compute $k$ disjoint branchings $B_1,\dots,B_k$ in a digraph
with sizes $\mu_1,\dots,\mu_k$, or to determine an optimal solution to the
matroidal degree-constrained augmentation version of the maximum term rank
problem.
- Endre Boros (Rutgers University)
Two-person zero-sum stochastic mean payoff games
I give an overview of this family of games, provide pseudo-polynomial algorithms
when there is limited randomness, and present some open ends and conjectures.
- Chandra Chekuri (University of Illinois, Urbana-Champaign)
Parallel algorithms for submodular function maximization
Submodular functions play a fundamental role in combinatorial optimization for their
applications as well as their elegant mathematical properties. In this talk we focus
on constrained submodular function maximization which is NP-Hard even in very restricted
settings. Good approximation algorithms can be obtained for many constraints of interest and a
number of new results and techniques have been developed in the last 15 years
that generalized and improved up on classical work from the late 70's. Very recently there has been a
new direction of interest, namely to find parallel and low-adaptivity algorithms. The talk will describe
some of these recent developments which demonstrate that, for several constraints of interest,
one can obtain parallel/low-adaptivity approximation algorithms whose guarantees essentially
match those of sequential algorithms.
Based on joint work with Kent Quanrud.
- Naoyuki Kamiyama (Kyushu University)
Matching problems under preferences with ties and matroid constraints
In this talk, I consider the situation where there exist two groups of agents,
and each agent has a preference list over the agents on the other side. Then the goal
is to find a good matching between these two groups for the preference
lists. In this talk, I consider the following two directions of generalization
of matching problems under preferences. The first direction is introduction of ties to the
preference lists. It is known that if there exist ties in the preference lists, then the situation
dramatically changes. The second direction is generalization of capacity constraints to
matroid constraints. Matroid constraints are important from not only the theoretical
viewpoint but also the practical viewpoint. In this talk, I talk about my recent results on
matching problems under preferences with ties and matroid constraints.
- Telikepalli Kavitha (Tata Institute of Fundamental Research)
Popular matchings: Good, bad, and mixed
We consider popular matchings in a bipartite graph G where every
vertex has strict preferences over its neighbors. Popular matchings are a
natural generalization of stable matchings and there are simple linear-time
algorithms to find a max-size (also, min-size) popular matching.
From an efficient algorithms point of view, there seem to be only a few
bright spots in the landscape of popular matchings. For instance, it is
NP-hard to decide if there exists a popular matching in G that is neither a
min-size nor a max-size popular matching. However if we generalize from
popular matchings to popular mixed matchings, then we can efficiently solve
the min-cost popular mixed matching problem (when there are edge costs);
moreover, the optimal mixed matching that we find has a simple structure.
- Yusuke Kobayashi (Kyoto University)
Restricted 2-matching problems
In a graph, an edge set M is said to be a 2-matching if each vertex is
incident to at most two edges in M. Finding a 2-matching of maximum size is
a classical combinatorial optimization problem, which can be solved
efficiently by using a matching algorithm. As an extension, the problem of
finding a maximum 2-matching without short cycles has attracted attentions,
because it has applications to approximation algorithms for TSP and its
variants. In this talk, I will talk about our recent results on such
problems.
- Euiwoong Lee (New York University)
The number of minimum k-cuts: Improving the Karger-Stein bound
Given an edge-weighted graph, how many minimum k-cuts can it
have? This is a fundamental question in the intersection of algorithms,
extremal combinatorics, and graph theory. It is particularly interesting in
that the best known bounds are algorithmic: they stem from algorithms that
compute the minimum k-cut. In 1994, Karger and Stein obtained a randomized
contraction algorithm that finds a minimum k-cut in O(n^{(2-o(1))k}) time.
It can also enumerate all such k-cuts in the same running time,
establishing a corresponding extremal bound of O(n^{(2-o(1))k}).
In this paper, we give an algorithm to enumerate all minimum k-cuts in
O(n^{(1.981+o(1))k}) time, breaking the algorithmic and extremal barriers
for enumerating minimum k-cuts. To obtain our result, we draw a new
connection between minimum k-cut and extremal set theory. In particular, we
give and use tighter bounds on the size of set systems with bounded dual
VC-dimension, which may be of independent interest.
Organizers
- Kazuhisa Makino (Kyoto University)
- Naoyuki Kamiyama (Kyushu University)
- Yusuku Kobayashi (Kyoto University)
- Yutaro Yamaguchi (Osaka University)