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.