• Kiyohito Nagano (Tokyo Tech)
• Yoshio Okamoto (Tokyo Tech, Chair)

Program

Abstracts

Kiyohito Nagano
Title: Submodular Function Minimization under Covering Constraints
Abstract:
In this talk, we consider the problems of minimizing nonnegative submodular
functions under covering constraints, which generalize the vertex cover,
edge cover, and set cover problems. We give approximation algorithms for
these problems exploiting the discrete convexity of submodular functions.
In addition, we give lower bounds on the approximability. This is a joint
work with Satoru Iwata.

Sang-il Oum
Title: Testing Branch-width at most k for fixed k or non-fixed k
Abstract:
An integer-valued function f on the set 2^V of all subsets of a finite
set V is a connectivity function if it satisfies the following
conditions: (1) f(X) + f(Y) ≥ f(X∩Y)+f(X∪Y) for all subsets X,Y of V,
(2)f(X)=f(V\X) for all X⊆V, and (3) f(∅) = 0.
Branch-width is defined for graphs, matroids, and more generally,
connectivity functions (symmetric submodular functions).
Given a connectivity function by an oracle, how efficient can you test
branch-width at most k?
I will present two results,
one jointly with Paul Seymour for the case when k is fixed, and
another by myself for the case when k is a part of an input.

Zoya Svitkina
Title: Asymmetric Traveling Salesman Path and Directed Latency Problems
Abstract:
The Traveling Salesman Problem (TSP) is one of the best-known NP-hard
problems in combinatorial optimization. There are two major versions
of the problem: the symmetric case, where the distance from any point
A to any other point B is assumed to be the same as the distance from
B to A, and the asymmetric case, where this is not necessarily true.
In both cases, the distances are assumed to satisfy the triangle
inequality. Another distinction that can be made is whether we are
interested in finding a cycle or a path that visits all the nodes.
These two versions are not equivalent, with the path version being, in
general, harder. In this work we study the asymmetric path version of
TSP, and we give a new approximation algorithm that also bounds the
integrality gap of a linear programming relaxation of the problem.

Related to TSP is the Minimum Latency problem, in which, as in TSP, we
wish to visit all of the given nodes. However, instead of minimizing the total
length of the tour (as in TSP), the objective is to minimize the sum
of waiting times of all the nodes. We study a directed (asymmetric)
version of this problem and design an approximation algorithm for it,
using our result for the asymmetric TSP path problem.

Naoyuki Kamiyama
Title: The Root Location Problem for Arc-disjoint Arborescences
Abstract:
Problems of determining the best location of facilities in given
networks under certain constraints (e.g., connectivity or flow
constraints) have recently been extensively studied in the fields
of operations research. In this talk, we introduce problems of
locating roots of arc-disjoint arborescence, and we investigate
the intractability of these problems and present a polynomial-time
algorithm for a certain class of efficiently solvable cases by
using the recent developments concerning with packing of arborescences.
This is a joint work with Satoru Fujishige (Kyoto University).

Vahab Mirrokni
Title: Recent developments in submodular maximization

Gagan Goel
Title: Algorithms for Multi-agent Combinatorial Problems with Submodular Cost Functions
Abstract:
In the algorithmic theory of combinatorial optimization, cost functions have
been chiefly modeled as additive. For instance, consider the network design
problem of min-cost spanning tree. We are given costs on the edges of a graph
G, and the cost of a subset of edges is just the additive sum. However, in
practice, the cost of building a large set of edges is typically smaller than
the sum. This work aims at designing algorithms for combinatorial optimization
problems under submodular cost functions, the class of all discrete functions
which satisfy the economies of scale property. We also consider the case when
there are multiple agents with their own cost functions, and each can build a
part of the whole solution.
Based on joint work with Chinmay Karande, Pushkar Tripathi, and Lei Wang.

Takuro Fukunaga
Title: Algorithms for Partitioning Hypergraphs and Submodular Systems
Abstract:
A k-cut of a hypergraph is a set of hyperedges whose removal divides the
hypergraph into k connected components. The hypergraph k-cut problem is
one of computing a minimum capacity k-cut. The submodular system k-partition
problem is a problem of partitioning a given finite set V into k non-empty
subsets V_1, V_2,..., V_k so that f(V_1)+f(V_2)+...+f(V_k) is minimized where f
is a non-negative submodular function on V. In this talk, we review recent
progress on algorithms for these problems.

Christian Sommer
Title: Distance Oracles for Sparse Graphs
Abstract:
We analyze the space requirements for data structures that assist shortest path
queries. Given is a graph with n nodes. A preprocessing algorithm computes a
data structure of size S.  If an algorithm computes approximate shortest paths
with multiplicative stretch at most alpha, it must access the data structure at
a certain number t of locations of the data structure. This three-way tradeoff
between size S, stretch alpha, and query time t is analyzed. (Announced
previously at FOCS 2009)