Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where it is required to order a given set of objects when the only available information among the objects is their pairwise similarity (or dissimilarity). Given the equivalence between the class of unit interval graphs and 0-1 Robinsonian matrices, we extend the famous 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval graphs. We introduce a generalization of Lex-BFS for weighted graphs, named Similarity-First-Search (SFS), and we present a multisweep polynomial time recognition algorithm based on a series of consecutive SFS sweeps. The algorithm is extremely simple and, given a symmetric matrix of size n, we show that it returns a Robinson ordering of the matrix after at most n-1 sweeps.

Suppose we are given a weighted graph $G=(V,E)$ and we have a total value equal to the maximum weight of a matching of $G$ to allocate among the vertices of $G$. Given any such allocation the excess of a subset of vertices $S$ is defined as the difference between the total value allocated to the vertices of $S$ and the weight of the maximum weight matching in the subgraph of $G$ induced by $S$. We study the problem of computing the set of all allocations that maximize the minimum excess of any subset of vertices. This problem is known to be solvable in polynomial time for instances where the maximum weight fractional matching has the same weight as the maximum weight matching, as well as for node-weighted graphs. In this talk we present recent results and methods for solving the problem on instances with general weights.

We consider the fundamental problem of exploring an undirected and initially unknown graph by an agent with little memory. The vertices of the graph are unlabeled, and the edges incident to a vertex have locally distinct labels. In this setting, it is known that log n bits of memory are necessary and sufficient to explore any graph with at most n vertices. We show that this memory requirement can be decreased significantly by making a part of the memory distributable in the form of pebbles. A pebble is a device that can be dropped to mark a vertex and can be collected when the agent returns to the vertex. We show that for an agent O(log log n) distinguishable pebbles and bits of memory are sufficient to explore any bounded-degree graph with at most n vertices. We match this result with a lower bound exhibiting that for any agent with sub-logarithmic memory, log log n distinguishable pebbles are necessary for exploration. This result will be presented at SODA 2016.

We develop a spatial branch-and-cut approach for nonconvex Quadratically Constrained Quadratic Programs with bounded complex variables (CQCQP). Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations of CQCQP. These valid inequalities are derived from the convex hull description of a nonconvex set of 2 by 2 positive semidefinite Hermitian matrices subject to rank-one constraint. We propose branching rules based on an alternative to a rank-one constraint that allows for local measurement of constraint violation. Closed-form bound tightening procedures are used to reduce the domain of the problem. We apply the algorithm to solve the Alternating Current Optimal Power Flow problem with complex variables and the Box-constrained Quadratic Programming problem with real variables.

Feasibility pump (FP) is a successful primal heuristic for mixed-integer linear programs (MILP). We observe that the randomization step used in classical FP may not be effective for decomposable instances. Our goal is to design a version of FP where the sparsity structure of constraint matrix is automatically used advantageously in the randomization step. In order to achieve this, we propose to incorporate a randomized algorithm for solving SAT instances called WalkSAT into the FP algorithm. Our contributions are: (i) We generalize WalkSAT for mixed-integer binary programs and prove this generalization maintains theoretical guarantees and properties of the original WalkSAT, such as smaller running-times for sparser and decomposable instances. (ii) We design a WalkSAT-based FP and give a theoretical analysis of its running time for decomposable subset-sum-type instances. To the best of our knowledge, this is the first time any theoretical analysis of running-time of FP or variants has been conducted. (iii) Suitable variants of the theoretical methods proposed were implemented. These versions produce a significant improvement in number of iterations, and therefore improve the running-times for finding feasible solutions to MIPLIB instances and randomly generated 2-stage stochastic MILPs.

We consider the problem of approximating the convex hull of the graph of a bilinear function on the n-cube. In particular, we are interested in bounds on the ratio of the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation and the difference between the concave and convex envelopes. Complementing a linear upper bound due to Luedtke, Namazifar and Linderoth, we prove a worst case lower bound of order square root of n. In addition, we characterize functions for which the McCormick hull equals the convex hull, and we describe the convex hulls for some additional functions. (joint work with Natashia Boland, Akshay Gupte, Fabian Rigterink and Hamish Waterer) 1) I have no preference and can accommodate both formats.

We give an overview of the current best approximation algorithms for fundamental clustering problems, such as k-center, k-median, k-means, and facility location. For the uncapacitated versions, a variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to a standard linear programming relaxation. This has given a uniform way of addressing these problems with often tight or nearly tight guarantees. Unfortunately, this collection of powerful algorithmic techniques is not easily applicable to the capacitated setting. In fact, there is no simple strong convex relaxation known for the capacitated versions. As a result, our understanding of these problems is significantly weaker and several fundamental questions remain open.

The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as k-means or k nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of such distances. We introduce a first attempt at using this lemma in the context of feasibility problems in linear programming. Length of talk: 30 minutes

We describe an algorithm that finds an ?-approximate solution to a concave mixed-integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/?, provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless P = NP. Comment: I strongly prefer a 30-minute talk over a 15-minute talk.

Perfect graphs were defined in the 1960s. Many problems about them were solved in the last decades, most notably the strong perfect graph conjecture and the recognition of perfect graphs in polytime. One problem is still open: finding a combinatorial algorithm to color perfect graphs. The goal of this talk is to present recent progresses toward this problem.

If you think about it for a second, you will realize or remember that the maximum degree $\Delta$ of a graph $G$ is an upper bound for the maximum clique size $\omega$ minus one. Thus, every graph $G$ obeys $\omega(G)\leq \Delta(G)+1$. Small graphs, like the path on three vertices, already testify that the reverse is not true. But even if we virtually blow up $\omega$ with any imaginable monotone function $f$, we will always find an insurgent $G$ revolting against the inequality $\Delta(G) \leq f(\omega(G))$. But can we detect all those rebels that deny $\Delta(G) \leq f(\omega(G))$, and if so, cherry-pick the (inclusionwise) smallest ones? A positive answer can be given in terms of a characterization of those smallest rebels. But doing so, immediatly the next question - of great interest from an algorithmic point of view - pops up: Is the number of such smallest insurgents finite? Although we remain short on a thoroughly satisfying answer, one insurgent that seems to be almost innocent is surprisingly revealed as the leader of the pack. This appears to be a good starting point to track down the rest...

In this talk, we give an introduction to the use of convex and concave envelopes in mixed integer nonlinear programming. Starting from basic definitions, we review some of the concepts that have led to the derivation of envelopes for families of functions. We illustrate that many of these results can be obtained through the use of combinatorial/integer programming tools including Lovasz extensions, disjunctive programming, and polyhedral partitions. We provide examples and conclude with extensions.

We investigate convex relaxations for the pooling problem, a nonconvex production planning problem in which products are mixed in intermediate pools in order to meet quality targets at their destinations. We characterize the extreme points of the convex hull of our non-convex set, and we derive valid nonlinear convex inequalities. Computational results demonstrate that the inequalities can significantly strengthen the convex relaxation of even the most sophisticated formulations of the pooling problem.

In MI(N)LP, non-contiguous domains of variables (or, stated differently, ‘holes’ in the domains) are usually expressed by auxiliary binary variables. We investigate MILP cutting planes that, instead of using this binary representation, are derived directly from the associated disjunctions. These cutting planes are a special case of generalized split cuts, and thus we call them wide split cuts. The validity of the holes can come from either primal or dual information, and we present computational results in both cases, based on time-indexed scheduling models and a lazy version of the 0-1 knapsack problem. We further explore an exact MILP approach based on these cutting planes, that in addition tackles non-contiguity directly via branching and as a side-effect reduces the model size.

I will survey recent results (some ours and some not) on solving polynomial optimization problems over sparse constraints. This field incorporates ideas from integer programming, linear programming and algebraic geometry. Polynomial optimization problems over continuous variables are strongly NP-hard in the sense that we can reduce standard binary integer programs to them, in a direct way. However there is an underlying additional difficulty caused by numerics, in particular the (non) existence of rational solutions.

We describe algorithms that optimize over certain structured subsets of the cone of positive semidefinite matrices (PSD cone) via linear programming and second order cone programming. Starting with an initial linear approximation of the PSD cone given by Ahmadi and Majumdar (2014), we improve the approximation in an iterative fashion using column generation. We apply our techniques to sum-of-squares (SOS) programming for nonconvex polynomial optimization problems, and to a copositive programming relaxation of the stable set problem.

In this work we investigate the behaviour of Dantzig Wolfe Decomposition when applied to Binary Quadratic Programming. Several decomposition are compared from a theoretical and experimental point of view. As test case we use the 0-1 k-item Quadratic Knapsack Problem. We show that with a proper reformulation we are able to close in the majority of the cases the whole integrality gap in a reasonable amount of time, solving to proven optimality more instances than a generic solver can do.

The selection of branching variables is a key component of branch-and-bound algorithms for solving Mixed-Integer Programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their "LP gains", which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 "tree" instances where we achieve a 5% geometric average time and node improvement, over the default rule of SCIP, a state-of-the-art MIP solver.

The software IPO is presented which investigates a polyhedron P given by means of an optimization oracle, e.g., a mixed-integer hull and a MIP solver. It detects all equations, can check adjacency of vertices, and compute some facets valid for P in exact arithmetic. In contrast to usual convex-hull algorithms which produce the entire description, but run out of resources for small dimensions already, IPO can handle much larger dimensions.

We study approximation schemes for a class of stochastic dynamic programs with several application areas, such as economics and supply chain management. The class is characterized by continuous state and action spaces, convex cost function, and affine transition function. A discrete analogue of this class is known to admit fully polynomial time approximation schemes (FPTASs). We prove that the continuous class under consideration does not admit an FPTAS, and in particular it admits neither relative nor additive approximations. To circumvent this hardness result, we introduce the concept of fully polynomial time ($\Sigma, \Pi$)- approximation schemes. That is, for every given additive error parameter $\Sigma > 0$ and multiplicative error factor $\Pi = 1 + \epsilon > 1$, the scheme returns a feasible solution whose value is at most $\Sigma + \Pi v^*$, where $v^* \ge 0$ is the optimal value, and it runs in time polynomial in the input size and in $\log(1\Sigma) + 1/\epsilon$. We develop fully polynomial time $(\Sigma, \Pi)$-approximation schemes for the class of continuous dynamic programs under consideration. While our method applies to continuous problems, the approximation scheme is combinatorial in nature. Our algorithmic results are achieved by extending to the continuous setting the technique of K-approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674–685]. This extension requires a completely new set of analytical and algorithmic tools that may be useful in their own right for further development of approximation algorithms. We perform a preliminary computational evaluation, showing that the proposed approximation scheme is orders of magnitude faster than solving the discretized problem exactly, and finds solutions of better quality than approximate solution approaches taken from the literature for comparable computational effort.

Photolithography is a process used by semi-conductor manufacturers to transfer the geometric pattern of a chip on a wafer. This is done by putting UV light through a photomask on a photoresistant layer on top of the wafer. If certain parts of the wafer do not need to be exposed, blades are moved in to block the UV light. Moving the blades is a time consuming process. Since it often influences the total processing time of a wafer in the lithography machine, minimizing the distance will reduce processing time. We formulate this problem as an adjusted form of the traveling salesman problem; the scenario a priori TSP problem. We show some complexity and approximation results for the problem and indicate computational results from a real-life setting. Optimizing the blading time turns out to reduce the total processing time by over 1 percent, which has a significant monetary impact, since the lithography machines are often the bottleneck in the factory and the production process is very expensive.

We answer the following question of Seymour: for which connected graphs H are there only finitely many 4-critical graphs that don't contain H as an induced subgraph? (A graph we call 4-critical if it is not 3-colorable, but every proper induced subgraph is.) This yields a certifying algorithm for the 3-colorability problem in the class of graphs without chordless paths on six vertices, which was an open problem posed by Golovach et al. Such an algorithm decides 3-colorability and proves that its answer, whether yes or no, is correct. Joint work with Maria Chudnovsky, Jan Goedgebeur and Mingxian Zhong

We study two basic graph parameters, the chromatic number and the orthogonal rank, in the context of classical and quantum exact communication complexity. In particular, we consider a promise equality problem, where Alice and Bob must decide if their inputs are equal or not. We prove that classical protocols for such problems can always be reduced to one-round protocols with no extra communication. In contrast, we give an explicit instance of a promise problem that exhibits an exponential gap between the one- and two-round exact quantum communication complexities. Whereas the chromatic number thus captures the complete complexity of promise equality problems, the hierarchy of “quantum chromatic numbers” (starting with the orthogonal rank) giving the quantum communication complexity for every fixed number of communication rounds thus turns out to enjoy a much richer structure. Moreover, we pose a conjecture on the orthogonality rank of a certain graph whose truth would imply an intriguing impossibility of round elimination in quantum protocols, something that works trivially in the classical case. Joint work with Jop Briet, Harry Buhrman,Debbie Leung and Florian Speelman.

We consider a class of fixed-charge transportation problems over a graph G. We show that this problem is strongly NP-hard, but can be solved in pseudo-polynomial time using dynamic programming if G is a tree. We also show that the linear programming formulation associated to the dynamic program can be obtained from extended formulations of single-node flow polytopes. Motivated by these results, we present a unary expansion-based formulation for general graphs that is computationally advantageous when compared to a standard formulation, even if its LP relaxation is not stronger.

In this talk, we will survey some recent conjectures related to the classical question: when does a convex body K contain a lattice point? A first satisfactory answer to this question, known as Khinchine's flatness theorem, states if K does not contain lattice points then K must be "flat", i.e. there must be a direction in which few lattice hyperplanes intersect K. Due to its connections with Integer Programming, quantitative improvements regarding "how flat" the body must be as a function of dimension were made by Lenstra, Kannan, Lovasz, Banaszczyk and others in the 80's and 90's. It is known however, that these bounds must be at least linear in the dimension. To circumvent this issue, we explore multidimensional extensions of flatness, first introduced by Kannan and Lovasz in 1988, where the only known lower bounds are logarithmic in dimension. As our main result, we show that a conjectured converse of Minkowski's first theorem (which relates the number of lattices points in a symmetric convex body to its volume) implies a very strong multidimensional flatness theorem when K is the Euclidean ball. Our proof relies on Fourier analysis, a novel convex relaxation together with a semidefinite rounding strategy. This is joint work with Oded Regev (NYU).

We introduce a concept that generalizes several different notions of a “centerpoint” in the literature. We develop an oracle-based algorithm for convex mixed-integer optimization based on centerpoints. Further, we show that algorithms based on centerpoints are “best possible” in a certain sense. Motivated by this, we establish several structural results about this concept and provide efficient algorithms for computing these points.

We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle's capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing methods for the stochastic VRP require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of trucks required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price (BCP) algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the stochastic VRP. Joint work with Thai Dinh and James Luedtke.

Measuring and managing risk has become crucial in modern decision making under stochastic uncertainty. In two-stage stochastic programming, mean risk models are essentially defined by a parametric recourse problem and a quantification of risk. Stability of such models with respect to perturbations of the underlying measure greatly depends on stability of the finite dimensional recourse problems. The talk addresses MILPs, QIPs and fairly general mixed-integer convex recourse models with additional integrality constraints and examines how classical results from parametric integer programming contribute to the stability of comprehensive classes of mean risk models.

The Firefighter problem was introduced by Hartnell (1995) as a natural model for optimal inhibition of harmful spreading phenomena on a graph. Despite considerable interest in the problem and progress on several fronts, our understanding of how well this and related problems can be approximated is still very limited. Interestingly, this is even true when the underlying graph is a spanning trees, which is one of the most-studied graph structures in this context. The Firefighter problem on trees is defined as follows. We are given a graph $G=(V,E)$ which is a spanning tree and a vertex $r\in V$, called \emph{root}. The problem is defined over discretized time steps. At time $0$, a fire starts at $r$ and spreads step by step to neighboring vertices. During each time step $1,2,\dots$, an arbitrary non-burning $v$ vertex can be protected, which prevents $v$ from burning in all future time steps. The goal is to find a protection strategy that maximizes the number of vertices that will not burn. A closely related problem, called Resource Minimization for Fire Containment (RMFC) on trees, was introduced by Chalermsook and Chuzhoy (2010). Here the task is to determine the smallest number $B\in \mathbb{Z}_{>0}$ such that if one can protect $B$ vertices at each time step (instead of just $1$), then there is a protection strategy such that none of the leaves of the tree will catch fire. The best known approximation algorithms for Firefighter and RMFC are $1-1/e$ (Cai, Verbin and Yang, 2008) and $\log^* n$ (Chalermsook and Chuzhoy, 2010), respectively. These algorithms are based on rounding of natural LP relaxations of the respective problems, for which matching integrality gap lower bounds are also proved. In this paper we show efficient algorithms with significantly better approximation ratios, thus showing that these bounds do not reflect the approximability thresholds of these problems. Concretely, we present a polynomial time approximation scheme (PTAS) for the Firefighter problem and an $O(1)$-approximation for RMFC, essentially matching the existing hardness results for the respective problems. To arrive at these results we use the natural LP relaxations for the respective problems in combination with various new techniques to go around the problem of large integrality gaps. Joint work with David Adjiashvili and Rico Zenklusen.

We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems --- including multi-constraint variants --- by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model. Our formulation is equivalent to Gilmore and Gomory's, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern. The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. We deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems.

Abstract: Solving a biobjective optimization problem requires enumerating all of its Pareto-optimal solutions. If the problem is a continuous linear program, the Pareto set can be obtained by applying techniques such as the parametric simplex method. For the mixed integer linear programming (MILP) case, one needs an implicit enumeration technique such as branch and bound (BB). Among the main features of such a BB algorithm is a set of fathoming rules to eliminate portions of the feasible set by proving that they contain no Pareto optimal solutions. We describe effective fathoming rules that only require a simple modification of the node problem and can be carried out very efficiently. (Joint work with Banu Soylu, Erciyes University, and Margaret Wiecek, Clemson University.)

The exact solution of bilevel optimization problems is a very challenging task that received more and more attention in recent years, as witnessed by the flourishing recent literature on this topic. In this paper we present ideas and algorithms to solve to proven optimality generic Mixed-Integer Bilevel Linear Programs (MIBLP's) where all constraints are linear, and some/all variables are required to take integer values. In doing so, we look for a general-purpose approach applicable to any MIBLP (under mild conditions), rather than ad-hoc methods for specific cases. Our approach concentrates on minimal additions required to convert an effective branch-and-cut MILP exact code into a valid MIBLP solver, thus inheriting the wide arsenal of MILP tools (cuts, branching rules, heuristics) available in modern solvers. Our main contributions can be summarized as follows: 1. We present a new family of Intersection Cuts (IC's) and Informed No Good (ING) cuts for MIBLP 2. Under mild assumptions (less restrictive than in most alternative proposals from the literature), we show that such cuts lead to an exact branch-and-cut algorithm for MIBLP's. 3. We present computational results for a very basic use of our cuts within a modern MILP solver (IBM ILOG Cplex 12.6.2), showing that the approach is comparable or better than alternative state-of-the-art methods. (joint work with Ivana Ljubic, Michele Monaci and Markus Sinnl)

We first briefly present two broad algorithmic frameworks for solving bilevel programs: a generalized Benders framework and a branch-and-cut framework. We discuss computational aspects of the implementation of algorithms based on these frameworks, which all require repeated solution of a parameterized integer program. Computational results will be presented.

The idea of k-adaptability in two-stage robust optimization is to calculate a fixed number k of second-stage policies here-and-now. After the actual scenario is revealed, the best of these policies is selected. This idea leads to a min-max-min problem. We consider the case where no first stage variables exist and propose to use this approach to solve combinatorial optimization problems with uncertainty in the objective function. We investigate the complexity of this special case for convex and discrete uncertainty. In the case of a convex uncertainty set, we are able to show that our problem is as easy as the underlying certain problem if k is greater than the number of variables and if we can optimize a linear function over the uncertainty set in polynomial time. In the case of a discrete uncertainty set with a fixed number of scenarios, we show, among other results, that the problem is weakly NP-hard and admits an FPTAS for the shortest path problem, the minimum spanning tree problem, and the knapsack problem, while it is tractable for the min-cut problem.

Due to the importance of robustness in many real-world optimization problems, the field of robust optimization has gained a lot of attention over the past decade. We concentrate on maximum flow problems and introduce a novel robust optimization model which, compared to known models from the literature, features several advantageous properties: (i) We consider a general class of path-based flow problems which can be used to model a large variety of network routing problems (and other packing problems). (ii) We aim at solutions that are robust against targeted attacks by a potent adversary who may attack any flow path of his choice on any edge of the network. (iii) In contrast to previous robust maximum flow models, for which no efficient algorithms are known, optimal robust flows for the most important basic variants of our model can be found in polynomial time. We also consider generalizations where the flow player can spend a budget to protect the network against the interdictor.

We study dynamic network flows in the presence of uncertainties in the input data. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T , while flow requires a certain travel time to traverse an arc. Ignoring uncertainties, a comprehensive theory exists including optimal solutions computable in polynomial time. Accounting for uncertain travel times, we investigate maximum flows over time under the assumption that at most g travel times may be delayed simultaneously. We develop and study a mathematical model for the corresponding robust counterpart under an algorithmic perspective. The problem is NP-hard as it generalizes the static robust flow problem. However, our dynamic version is considerably more complex: we show that it is NP-hard to verify feasibility of a given candidate solution. Furthermore, we show that the existing concept of temporally repeated flows no longer provides optimal solutions, but rather yields a worst case optimality gap of at least T . We finally show that for infinite delays, the optimality gap is at most O(k log T), where k is a newly introduced instance characteristic. 1) have no preference and can accommodate both formats;

In this talk, I will describe a simple iterative method for proving a variety of exact and approximate results in combinatorial optimization. It is inspired by Jain's iterative rounding method for designing approximation algorithms for survivable network design problems, and developed further with a relaxation idea in the work of Lau and Singh in their work on designing the approximation algorithm for the degree bounded spanning tree problem. I will give an introduction to these methods and point to its power in proving a large set of results.

I will discuss some new approaches to rounding solutions to a linear program, based on techniques from discrepancy. This method generalizes and combines the advantages of both randomized and iterated rounding, and leads to several new refined bounds for various classical problems in discrete optimization. Joint work with Viswanath Nagarajan.

\emph{Diversity maximization} is an important concept in information retrieval, computational geometry and operations research. Usually, it is a variant of the following problem: Given a ground set, constraints, and a function $f(\cdot)$ that measures diversity of a subset, the task is to select a feasible subset $S$ such that $f(S)$ is maximized. The \emph{sum-dispersion} function $f(S) = \sum_{x,y \in S} d(x,y)$, which is the sum of the pairwise distances in $S$, is in this context a prominent diversification measure. The corresponding diversity maximization is the \emph{max-sum} or \emph{sum-sum diversification}. Many recent results deal with the design of constant-factor approximation algorithms of diversification problems involving sum-dispersion function under a matroid constraint. In this paper, we present a PTAS for the max-sum diversification problem under a matroid constraint for distances $d(\cdot,\cdot)$ of \emph{negative type}. Distances of negative type are, for example, metric distances stemming from the $\ell_2$ and $\ell_1$ norm, as well as the cosine or spherical, or Jaccard distance which are popular similarity metrics in web and image search.

Network infrastructures are a common phenomenon. Network upgrades and expansions typically occur over time due to budget constraints. We introduce a class of incremental network design problems that allow investigation of many of the key issues related to the choice and timing of infrastructure expansions and their impact on the costs of the activities performed on that infrastructure. We examine three variants: incremental network design with shortest paths, incremental network design with maximum flows, and incremental design with minimum spanning trees. We investigate their computational complexity, we analyze the performance of natural heuristics, we derive approximation algorithms, and we study integer program formulations.

In this talk, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. For each of these problems: (i) We first present a method to describe the sparsity structure of the constraint matrix. This method is different for the different types of problems. (ii) We present a method to describe a hierarchy of cutting-planes from very sparse to completely dense. (iii) Assume that we decide on the support of sparse cutting-planes and the strongest inequalities on these supports are added. Call the optimal objective function value of the linear programming relaxation together with these cuts as zcut. We present bounds on the ratio of zcut and the optimal objective function value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. There results also shed light on the strength of scenario-specific cuts for two stage stochastic MILPs. This is joint work with Marco Molinaro and Qianyi Wang.