Speaker: Vitaly A. Strusevich (University of Greenwich, London, U.K.)
Title: Linking Optimization Problems with Submodular Constraints to Scheduling with Controllable Processing Times
Joint work with: Akiyoshi Shioura (Tohuku University, Sendai, Japan) and Natalia V. Shakhlevich (University of Leeds, Leeds, U.K.).
Abstract:
We show how various scheduling problems on parallel machines with
controllable processing times, release dates and deadlines can be
reformulated in terms of linear programming problems over a submodular
polyhedron intersected with the box. To solve the resulting LP problem
we develop a decomposition algorithm which leads to the fastest known
algorithms for the initial scheduling problems of minimizing total
compression cost. The approach can be extended to handling bicriteria
scheduling problems of finding Pareto optima for the maximum completion
time and total compression cost as the two objectives. Again, for the
bicriteria scheduling, the submodular optimization approach
considerably improves previously known results.
Speaker: Rico Zenklusen (ETH Zurich)
Title: Submodular Maximization via Contention Resolution Schemes
Joint work with: Chandra Chekuri and Jan Vondrák.
Abstract:
Due to the property of diminishing returns, submodular functions
naturally appear in many optimization settings. Thus, considerable
interest arose in the question how to approximately maximize them under
various constraints. I will present a quite broadly applicable
framework that allows for obtaining strong algorithms to approximately
maximize submodular functions subject to a variety of packing
constraints. Our approach is based on a relaxation and rounding
framework. Similar approaches have been used previously, however, only
in much more limited settings. We overcome several limitations to
obtain a general framework, which reduces the problem to finding a
particular type of rounding algorithm, a contention resolution scheme,
which only depends on the constraints.
Speaker: Hadas Shachnai
Title: The All-or-Nothing Generalized Assignment Problem
Joint work with: Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, and Tami Tamir.
Abstract:
We study a variant of the {\em generalized assignment problem} (GAP)
which we label {\em all-or-nothing GAP} (AGAP)}. We are given a set of
items, partitioned into $n$ groups, and a set of $m$ bins.
Each item $\ell$ has size $s_\ell >0$, and utility $a_{\ell j} \geq
0$ if packed in bin $j$. Each bin can accommodate at most one item from
each group, and the total size of the items in a bin cannot exceed its
capacity.
A group of items is {\em satisfied}
if all of its items are packed. The goal is to find a feasible packing
of a subset of the items in the bins such that the total utility from
satisfied groups is maximized. We motivate the study of AGAP by
pointing out a central application in scheduling advertising campaigns.
Our main result is an
$O(1)$-approximation algorithm for AGAP instances arising in practice,
where each group consists of at most $m/2$ items. Our algorithm
uses a novel reduction of AGAP to maximizing submodular function
subject to a matroid constraint. For AGAP instances with fixed number
of bins, we develop a randomized polynomial time approximation scheme (PTAS),
relying on a non-trivial LP relaxation of the problem. We further
obtain for other special cases small constant approximation algorithms
and PTASs.
Speaker: Hiroshi Hirai
Title: Discrete Convexity for Multiflows and 0-extensions
Abstract:
This paper addresses an approach to extend the
submodularity/L-convexity concepts to more general structures than the
integer lattices.
The main motivations are (i) to solve the tractability classification
of minimum 0-extension problem, and (ii) to give a
discrete-convex-analysis view to the duality of a class of
multicommodity flow problems.
Speaker: Andreas Krause
Title: Distributed Submodular Maximization: Identifying Representative Elements in Massive Data Sets
Joint work with: Baharan Mirzasoleiman, Amin Karbasi and Rik Sarkar.
Abstract:
Many large-scale machine learning problems (such as clustering,
non-parametric learning, kernel machines, etc.) require selecting, out
of a massive data set, a manageable yet representative subset. Such
problems can often be reduced to maximizing a monotone submodular set
function subject to cardinality constraints. Classical approaches require
centralized access to the full data set; but for truly large-scale
problems, rendering the data centrally is often impractical. In this
talk, I will discuss some recent work on submodular function
maximization in a distributed setting. We consider a simple, two-stage
protocol, that is easily implemented using MapReduce style
computations. We theoretically analyze it, and show, that under certain
natural conditions, performance close to the centralized approach can
be achieved. In an extensive experimental study, we demonstrate the
effectiveness of our approach on several applications, including sparse
Gaussian process inference on tens of millions of data points using
Hadoop.
Speaker: Shin-Ichi Tanigawa
Title: Generalized Skew Bisubmodularity
Abstract:
Bisubmodular functions are a natural signed extension of submodular
functions. Huber, Krokhin, and Powell (SODA 2013) introduced a concept
of skew bisubmodularity, as a generalization of bisubmodularity, in
their complexity dichotomy theorem for valued constraint satisfaction
problems over the three-value domain. In this paper we consider a
natural generalization of the concept of skew bisubmodularity and show
a connection between the generalized skew bisubmodularity and a convex
extension over rectangles. We also give a combinatorial algorithm by
extending the bisubmodular function minimization algorithm by McCormick
and Fujishige. This is a joint work with Satoru Fujishige and Yuichi
Yoshida.
Speaker: Maurice Queyranne, Sauder School of Business, University of British Columbia, Vancouver, B.C., Canada
Title: Carathéodory, Helly and Radon Numbers for Sublattice Convexities
Joint work with: Fabio Tardella (Facoltà di Economia, Sapienza Università di Roma)
Abstract:
The Carathéodory, Helly, and Radon numbers are three main invariants in
convexity theory. They have been determined, exactly or approximately,
for a number of different convexity structures. We present new results
on the exact Carathéodory numbers for the convexities defined by
sublattices of d-dimensional Euclidian, integer and Boolean vector
spaces. Our results imply, for example, that if a subset S of a
d-element set D can be obtained with unions and intersections from a
given family G of subsets of D, then S can be obtained with
unions and intersections from a small subfamily of G. We also
consider convexities induced by polyhedra defined by dual (generalized)
network flow constraint systems. We determine the Helly and
Radon numbers of such convexities, and very close upper and lower
bounds for their Carathéodory numbers. In particular, for the
L-natural convexities this number is the optimum value of a problem in
extremal combinatorics, namely, the maximum size of a minimal cover of
all pairs of elements from a (d+1)-element set with permutations of
that set.
Speaker: Zoltán Szigeti
Title: Matroid-based Packing of Arborescences
Joint work with: Olivier Durand De Gevigney and Viet-Hang Nguyen.
Abstract:
We provide the directed counterpart of a slight extension of Katoh and
Tanigawa’s result on rooted-tree decompositions with matroid
constraints. Our result characterizes digraphs having a packing of
arborescences with matroid constraints. It is a proper extension of
Edmonds’ result on packing of spanning arborescences and implies -
using a general orientation result of Frank - the above result of Katoh
and Tanigawa.
Speaker: Gyula Pap
Title: Blocking k-arborescences
Abstract:
Given a digraph D, and a non-negative integer k, a subgraph of D is
called a k-arborescence if it is the arc-disjoint union of k
arborescences. Note that the root is not fixed, that is, the k root
nodes are chosen arbitrarily, also allowing them to coincide. It is a
polynomial time solvable problem to find a k-arborescence, or determine
that there is no such subgraph - which is characterized by a
sub-partition constraint.
In the talk we consider the following problem: given D and k, find a
minimum number of arcs so that their deletion destroys all
k-arborescences. In other words, find a minimum cardinality set of arcs
to block all k-arborescences. The main result here is that this problem
still is solvable in polynomial time. The solution of the problem is
based on a result of Barasz, Becker, Frank saying that the family of
so-called in-solid sets has the Helly property. (A set of nodes is
called in-solid if all of its proper subsets has a larger number of
in-coming arcs.)
Speaker: Jose Soto
Title: Minimizing symmetric submodular functions under hereditary constraints
Joint work with: Michel Goemans
Abstract:
We present an efficient algorithm to find nonempty minimizers of a
symmetric submodular function $f$ over any family of sets $\calI$
closed under inclusion.
Our algorithm makes $O(n^3)$ oracle calls to $f$ and $\calI$, where $n$
is the cardinality of the ground set. In contrast, the problem of
minimizing a general submodular function under a cardinality constraint
is known to be inapproximable within $o(\sqrt{n/\log n})$ (Svitkina and
Fleischer [2008]).
Our algorithm is similar to a procedure by Nagamochi and Ibaraki [1998]
that finds all nontrivial inclusionwise minimal minimizers of a
symmetric submodular function over a set of size $n$ using $O(n^3)$
oracle calls. Their procedure in turn is based on Queyranne's algorithm
[1998] to minimize a symmetric submodular function by finding so called
pendent pairs.
Speaker: Thomas Rothvoss (MIT)
Title: Polynomiality for Bin Packing with a Constant Number of Item Types
Joint work with: Michel X. Goemans.
Abstract: We consider the bin
packing problem with d different item sizes s_i and item multiplicities
a_i, where all numbers are given in binary encoding.
This problem formulation is also known as the 1-dimensional cutting stock problem.
In this work, we provide an algorithm which, for constant d, solves bin
packing in polynomial time. This was an open problem for all d >= 3.
In fact, for constant d our algorithm solves the following problem in
polynomial time: given two d-dimensional polytopes P and Q,
find the smallest number of integer points in P whose sum lies in Q.
Speaker: Olivier Durand de Gevigney
Title: Orientation of Graphs and Connectivity
Abstract:
Graphs having a k-arc-connected orientation were characterized by
Nash-Williams. This characterization is now well understood and Frank
showed that the submodular flow technique is a successful approach.
However achieving k-vertex-connectivity by orientation is still a
challenging problem.
Frank conjectured a characterization of graphs having a
k-vertex-connected orientation. The case k=2 for Eulerian graphs was
proved by Berg and Jordán. We disprove this conjecture and prove that,
given k>=3, deciding whether a graph has a k-vertex-orientation is
NP-complete.
This result leads us to focus on a earlier conjecture of Thomassen
stating that, for every integer k, there exists a least integer f(k)
such that every f(k) vertex-connected graphs has a k-vertex-connected
orientation. This conjecture is proved for k=2 by Jordán with
f(2)<=18 using matroid theory. Cheriyan, Szigeti and I improved this
lower bound to f(2)<=14. The cases k>=3 are still open.
Speaker: Fabio Tardella
Title: Linear optimization over hypergraph and integer generalized submodular polyhedra
Abstract: Two new generalizations of polymatroids and submodular polyhedra are proposed.
The first one, Z-submodular polyhedra, also generalizes Fujishige's
ternary semimodular polyhedra which in turn extend generalized
polymatroids and intersections of submodular and supermodular
polyhedra. Linear optimization can be solved in pseudopolynomial time
over Z-submodular polyhedra through separation and the ellipsoid
algorithm.
In the second one, (hyper)graph submodular polyhedra, a variable is
associated to each (hyper)egde of a (hyper)graph and one requires that
the sum of all variables associated with edges connecting vertices in a
given set S is not greater than the value of a submodular function
f(S).
Linear optimization can be solved in polynomial time, again through
separation and the ellipsoid algorithm, over general (hyper)graph
submodular polyhedra. In a special case, with an interesting
application to a probability bounding problem, it is shown that linear
optimization reduces to a minimum spanning tree problem and can thus be
solved by a greedy algorithm.