*Institut d'Etudes Scientifiques de Cargèse*, Corsica (France). September 30th - October 5th, 2013.

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.).

Speaker: Rico Zenklusen (ETH Zurich)

Title: Submodular Maximization via Contention Resolution Schemes

Joint work with: Chandra Chekuri and Jan Vondrák.

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.

Speaker: Hiroshi Hirai

Title: Discrete Convexity for Multiflows and 0-extensions

Speaker: Andreas Krause

Title: Distributed Submodular Maximization: Identifying Representative Elements in Massive Data Sets

Joint work with: Baharan Mirzasoleiman, Amin Karbasi and Rik Sarkar.

Speaker: Shin-Ichi Tanigawa

Title: Generalized Skew Bisubmodularity

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)

Speaker: Zoltán Szigeti

Title: Matroid-based Packing of Arborescences

Joint work with: Olivier Durand De Gevigney and Viet-Hang Nguyen.

Speaker: Gyula Pap

Title: Blocking k-arborescences

Speaker: Jose Soto

Title: Minimizing symmetric submodular functions under hereditary constraints

Joint work with: Michel Goemans

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

Speaker: Fabio Tardella

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.

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.)

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.

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.

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.

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.