• Combinatorial Optimization
• Rigidity Workshop

• Schedule
• Participants

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios.

In this work we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

The Fujishige-Wolfe heuristic is empirically one of the fastest algorithms for Submodular Function Minimization and is based upon Wolfe's algorithm to find the nearest point on a polytope to the origin. There was no theoretical guarantees known for the same. In this work we give a convergence analysis for Wolfe's algorithm which implies a pseudopolynomial running time for the Fujishige Wolfe algorithm.

A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems are often too large to be solved on a single machine. In this talk, we describe a simple distributed algorithm that is embarrassingly parallel and it achieves provable, constant factor, worst-case approximation guarantees. We demonstrate its efficiency in large problems with different kinds of constraints with objective values always close to what is achievable in the centralized setting.

This is joint work with Rafael Barbosa, Huy Nguyen and Justin Ward.

Consider the problem of selecting k items that maximize the value of a monotone submodular set function f, in a setting in which f can be accessed using value queries. It is well known that in this setting polynomially many queries suffice in order to obtain an approximation ratio of (1 - 1/e). We consider a variation on this problem in which the value queries are required to be of uniform size: each queried set, like the desired solution itself, must contain k items. We show that polynomially many uniform size queries suffice in order to obtain an approximation ratio of 1/2, and that an approximation ratio of (1+ε)/2 requires a number of queries that is exponential in (ε k). For the interesting special case of coverage functions, we show that an approximation ratio strictly better than 1/2 is attainable with polynomially many uniform size queries.

We consider the NP-hard problem of maximizing a monotone submodular function over a matroid constraint. Vondrak's continuous greedy algorithm achieves the best possible approximation ratio 1-1/e using continuous methods. Can the same be accomplished combinatorially? We show that this is arguably the case, by giving a simple local search algorithm with matching performance. The algorithm uses a sophisticated auxiliary objective function whose provenance we explore in the talk.

Joint work with Justin Ward.

The notion of total dual integrality proved decisive in combinatorial optimization since it properly captured a phenomenon behind the tractability of weighted optimization problems. For example, we are able to solve not only the maximum cardinality matching (degree-constrained subdigraph, matroid intersection, shortest path, etc.) problem but its weighted or min-cost version as well, and this is so because the describing linear system in the background is TDI.

There are, however, natural combinatorial optimization problems where the cardinality case is nicely doable while the min-cost version is NP-complete, and hence the possible existence of a TDI-description is out of question. A well-known example of this type is the strongly connected augmentation problem – solved by Eswaran and Tarjan – while a much less known but equally exciting example is the max term-rank problem – solved by Ryser – which is about finding a simple bipartite graph with a specified degree prescription for which the matching number is as large as possible.

In this talk, we recall the Supermodular covering theorem by Frank and Jordán that turned out to be responsible for the solvability of several non-TDI graph-optimization problems. After outlining some older applications, we describe new ones concerning degree-constrained and matroidal generalization of the term-rank problem, root-edge constrained extensions of the disjoint arborescences theorem of Edmonds, and various problems on connectivity augmentation with simple digraphs. Though the general form of the Supermodular covering theorem cannot be extended so as to concern simple digraphs since such an extension would include NP-complete graph-optimization problems, we introduce a special framework where it can, and this is behind the new applications.

Great part of the new results are joint work with Kristóf Bérczi.

Huber, Krokhin, and Powell (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, and they showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige, Tanigawa, and Yoshida (2014) also showed a min-max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular functions was left open.

In this talk we give combinatorial polynomial algorithms for skew-bisubmodular function minimization by adapting the combinatorial polynomial algorithms for bisubmodular function minimization by Fujishige and Iwata (2005) and McCormick and Fujishige (2010). Here we need a new concept of augmenting-path sequence and a new technique of treating auxiliary networks and conditioning graphs.

This is joint work with Shin-ichi Tanigawa.

A point-line framework is a collection of points and lines in the plane which are linked by pairwise constraints that fix some angles between pairs of lines and also some point-line and point-point distances. It is rigid if every continuous motion of the points and lines which preserves the constraints results in a point-line framework which can be obtained from the initial framework by a translation or a rotation. I will describe a characterization of when a generic point-line framework is rigid, and an open problem of characterizing generic rigidity for point-line frameworks with parallel classes of lines.

This is joint work with John Owen (Siemens, Cambridge).

A graph G = (V, E) is called (k, l)-tight if |E(X)| ≤ k|X| - l for all subset X of nodes in G with |X| ≥ 2 and |E| = k|V| - l. A graph G is called (k, l)-redundant if G - e has a spanning (k, l)-tight subgraph for all edge e in E. We consider the following augmentation problem. Given a graph G = (V, E) that has a (k, l)- tight spanning subgraph, find a graph H = (V, F) with minimum number of edges, such that G + H is (k, l)-redundant.

We give a polynomial algorithm for this augmentation problem for k ≥ l. We also give a polynomial algorithm for the case where G is a (k, l)-tight graph with k < l ≤ 3/2 k. (We note that in the case of l = 3/2 k the original problem is NP-hard.) As (k, l)-tight graphs play an important role in rigidity theory, these algorithms can be used to make several types of bar-joint frameworks redundantly rigid by adding a smallest set of new bars.

For an undirected graph and a fixed integer k, a simple 2-matching is said to be C_k-free if it has no cycle of length k or less. The problem of finding a maximum cardinality C_k-free 2-matching is polynomially solvable when k ≤ 3, and NP-hard when k ≥ 5. It is known that the polynomial solvability of this problem is closely related to jump systems. Indeed, the degree sequences of the C_k-free 2-matchings form a jump system for k ≤ 4, and do not always form a jump system for k ≥ 5. As a quantitative extension of these results, we investigate a relationship between weighted C_k-free 2-matchings and M-concave functions on constant-parity jump systems. It is known that the weighted C_k-free 2-matchings induce an M-concave function on a constant-parity jump system for k ≤ 2, and it is not always true for k ≥ 4, which is consistent with the polynomial solvability of the maximization problem. In this talk, we show that the weighted C₃-free 2-matchings induce an M-concave function on a constant-parity jump system.

In this talk we will present a new cutting plane method and show how this technique can be used to achieve faster asymptotic running times for fundamental problems in combinatorial optimization. In the first part of this talk Yin Tat Lee will provide an overview of cutting plane methods and demonstrate how it can be used to improve the running time for classic problems such as matroid intersection. In the second part of the talk Aaron Sidford will discuss how these techniques can be used to achieve improved weakly and strongly polynomial running times for submodular function minimization.

This talk is based on joint work between Yin Tat Lee, Aaron Sidford, and Sam Wong and is based primarily on A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization <http://arxiv.org/abs/1508.04874> to appear in FOCS 2015.

One of the main results of "Order-Based Cost Optimization in Assemble-to-Order Systems" by Y. Lu and J-S. Song, Operations Research, 53, 151-169 (2005) is Proposition 1 (c), which states that the cost function of an assemble-to-order (ATO) inventory system satisfies a discrete convexity property called L^♮-convexity. We construct a counterexample showing that this result is incorrect. We then show how to use two existing algorithms to solve the underlying problem in pseudopolynomial time, and that such problems cannot in general be solved in polynomial time. Lastly we note that our counterexample can  be adapted to show that some ideas for trying to show discrete convexity in this ATO model do not work.

Joint work with A. Bolandnazar, W.T. Huh, and K. Murota.

Submodular functions are widely recognized as a discrete analogue of convex functions. This convexity view of submodularity was established in the early 1980's by the fundamental works of A. Frank, S. Fujishige and L. Lovasz. Discrete convex analysis extends this view to broader classes of discrete functions by introducing the concepts of L-convex and M-convex functions, which are functions defined on the integer lattice. The following issues are discussed in discrete convex analysis:

• Extensibility to (ordinary) convex functions in real variables,
• Local characterization of global minimality,
• Discrete duality, such as Fenchel-type min-max relation and separation theorem,
• Conjugacy relationship between L-convex and M-convex functions under the Legendre-Fenchel transformation.

Besides L-convex and M-convex functions, a number of related concepts are proposed in the literature, including integrally-convex functions, M-convex functions on jump systems, and L-convex functions on graphs. In this talk we compare those concepts in terms of the above properties together with the motivations of the concepts.

I will survey recent progress on submodular maximization, both constrained and unconstrained, and for both monotone and non-monotone submodular functions.

We consider the rigidity of graphs realised on concentric d-spheres in d+1 dimensions where the radii of the spheres are allowed to vary independently. To do this we use coloured graphs and realisations of these graphs where vertices with the same colour correspond to spheres whose radii vary at the same rate. For d=1 with arbitrary number of colours and for d=2 with at most 3 colours we provide characterisations of generic rigidity in terms of count functions on these coloured graphs.

We consider the problem of maximizing a nonnegative submodular set function f: 2^ℕ → ℝ⁺ subject to a p-matchoid constraint in the single-pass streaming setting. Previous work in this context has considered streaming algorithms for modular functions and monotone submodular functions. The main result is for submodular functions that are non-monotone. We describe deterministic and randomized algorithms that obtain a Ω(1/p)-approximation using O(k log k)-space, where k is an upper bound on the cardinality of the desired set. The model assumes value oracle access to f and membership oracles for the matroids defining the p-matchoid constraint.

Joint work with Chandra Chekuri and Shalmoli Gupta.

Scene analysis is concerned with the reconstruction of d-dimensional objects, such as polyhedral surfaces, from (d-1)-dimensional pictures (i.e., projections of the objects onto a hyperplane). This theory is closely connected to rigidity theory and other areas of discrete applied geometry, and it also has important practical applications in Artificial Intelligence and Computer Vision.

In this talk we study the impact of symmetry on the lifting properties of pictures. We first use methods from group representation theory to derive new necessary conditions for a picture with a non-trivial symmetry group in an arbitrary dimension to be minimally flat (i.e., non-liftable). These conditions imply very simply stated restrictions on the number of those structural components of the picture that are fixed by the elements of its symmetry group. We then show that these conditions, together with the standard non-symmetric counts, are also sufficient for a plane picture which is generic with three-fold rotational symmetry C₃ to be minimally flat. This combinatorial characterization of minimally flat C₃-generic pictures is obtained via a new inductive construction scheme for symmetric sparse hypergraphs. Finally, we also give a sufficient condition for sharpness of pictures with C₃ symmetry.

This is joint work with Viktoria Kaszanitzky.

We analyze minimization algorithms for L-convex functions in discrete convex analysis, and establish exact bounds for the number of iterations required by the steepest descent algorithm and its variants. We also mention the implication of our results to iterative auction algorithms in auction theory.

We study a variant of the online bipartite matching problem that we call the online matroid intersection problem. For two matroids M1 and M2 defined on the same ground set E, the problem is to design an algorithm that constructs the largest common independent set in an online fashion. At each step, the algorithm is presented with an element in random order and must irrevocably decide whether to pick the element, while always maintaining an independent set in both the matroids. Since the natural greedy algorithm has a half competitive ratio, the question is whether we can beat half. This problem generalizes online bipartite matching in the edge arrival model where a random edge is presented at each step; nothing better than half was known previously.

In this paper, we present a simple randomized algorithm that has a 1/2 + ε competitive ratio in expectation, where the expectation is over the randomness of the input order and the coin tosses of the algorithm, for some ε > 10^-5. We also extend our online bipartite matching result to general graphs, a case not captured by matroid intersection. Our analysis uses techniques initially developed for the streaming model and our results are also interesting in this setting.

This is joint work with Guru Prashanth Guruganesh.

Maximizing monotone submodular function under a certain constraint has been intensively studied in the last decade and it is now recognized as a powerful framework for various machine learning problems. In this talk, we consider generalized monotone submodular function maximization over the integer lattice and present polynomial time approximation algorithms for various constraints. We also discuss its applications on machine learning tasks.

A graph is called globally rigid (or uniquely realizable) if for any generic embedding of it in d-dimensional Euclidean space there is no other embedding with the same edge-lengths (up to congruence). The global rigidity of graphs is one of the central topics in rigidity theory, and two major breakthroughs have been done in the past decade. In 2005 Jackson and Jordan gave a combinatorial characterization of 2-dimensional global rigidity by solving Connelly's conjecture on the inductive construction of 3-connected redundantly rigid graphs. In 2010 Gortler, Healy, and Thurston gave a characterization of d-dimensional global rigidity in terms of the corank of the Laplacian weighted by "self-stresses". However establishing a combinatorial characterization for higher dimension (especially for three dimension) remains a challenging open problem. In this talk I would talk about recent progress on this subject and possible extensions of new techniques.

I will discuss rigidity properties of binomial random graphs G(n,p(n)) in fixed dimension d and some related problems in low-rank matrix completion. The threshold for rigidity is p(n) = Θ(log n / n), which is within a multiplicative constant of optimal.

This talk is based on joint work with Franz Király.

The stable matching model of Gale and Shapley (1962) has been generalized in various directions such as matroid kernels due to Fleiner (2001) and stable allocations in bipartite networks due to Baiou and Balinski (2002). Unifying these generalizations, we introduce a concept of stable allocations in polymatroid intersection.

Our framework includes both integer- and real-variable versions. The integer-variable version corresponds to a special case of the discrete-concave function model due to Eguchi, Fujishige, and Tamura (2003), who established the existence of a stable allocation by showing that a simple extension of the deferred acceptance algorithm of Gale and Shapley finds a stable allocation in pseudo-polynomial time. It has been open to develop a polynomial time algorithm even for our special case.

In this talk, we present the first strongly polynomial algorithm for finding a stable allocation in polymatroid intersection. To achieve this, we utilize the augmenting path technique for polymatroid intersection. In each iteration, the algorithm searches for an augmenting path by simulating a chain of proposes and rejects in the deferred acceptance algorithm. The running time of our algorithm is O(n³γ), where n and γ respectively denote the cardinality of the ground set and the time for computing the saturation and exchange capacities. This is as fast as the best known algorithm for the polymatroid intersection problem.

This is joint work with Satoru Iwata.

An effective technique for solving optimization problems over massive data sets is to partition the data into smaller pieces, solve the problem on each piece and compute a representative solution from it, and finally obtain a solution inside the union of the representative solutions for all pieces. This technique can be captured via the concept of composable core-sets, and has been recently applied to solve diversity maximization problems as well as several clustering problems. However, for coverage and submodular maximization problems, impossibility bounds are known for this technique. In this paper, we focus on efficient construction of a randomized variant of composable core-sets where the above idea is applied on a random clustering of the data. We employ this technique for the diversity, coverage, monotone and non-monotone submodular problems. Our results significantly improve upon the hardness results for non-randomized core-sets, and imply improved results for submodular maximization in a distributed and streaming settings.

In summary, we show that a simple greedy algorithm results in a 1/3-approximate randomized composable core-set for submodular maximization under a cardinality constraint. Our result also extends to non-monotone submodular functions, and leads to the first 2-round MapReduce-based constant factor approximation algorithm with O(n) total communication complexity for either monotone or non-monotone functions. Finally, using an improved analysis technique and a new algorithm PseudoGreedy, we present an improved 0.545-approximation algorithm for monotone submodular maximization, which is in turn the first MapReduce-based algorithm beating factor 1/2 in a constant number of rounds. We also provide improved approximate core-sets for diversity maximization.

During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. The strong interest in MSPs is due to both its many applications and the fact that matroid constraints have useful properties for the design of strong online algorithms. Partially linked to its numerous applications, interest arose in nonlinear versions of MSP, and in particular in the submodular matroid secretary problem (SMSP), where a submodular function has to be maximized by choosing elements of the ground set online. We present a close link between MSP and SMSP, showing a black-box reduction to transform algorithms for MSP to algorithms for SMSP. This leads to many first and improved O(1)-competitive algorithms for SMSP on various matroid classes by exploiting results on MSP. Furthermore, our reduction implies an O(log log(rank))-competitive algorithm for SMSP, thus matching the currently best algorithm for MSP, and improving on the previously best O(log(rank))-competitive algorithm for SMSP. A further implication of our reduction is that the matroid secretary conjecture is equivalent to the same conjecture for SMSP.

This is joint work with Moran Feldman.

In this talk, we survey recent results on the power of LP relaxations (the basic LP relaxation and Sherali-Adams relaxations) in the context of valued constraint satisfaction problems (VCSP). We give precise characterisations of constraint languages for which these relaxations are exact, and also discuss computational complexity consequences.