Publications related to Upper and lower bounds

Decision Rule Bounds for Two-Stage Stochastic Bilevel Programs

We study stochastic bilevel programs where the leader chooses a binary here-and-now decision and the follower responds with a continuous wait-and-see-decision. Using modern decision rule approximations, we construct lower bounds on an optimistic version an ...

2018

epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

Jian Li, Lingxiao Huang

We study the problem of constructing epsilon-coresets for the (k, z)-clustering problem in a doubling metric M(X, d). An epsilon-coreset is a weighted subset S subset of X with weight function w : S -> R->= 0, such that for any k-subset C is an element of ...

IEEE COMPUTER SOC2018

Robust Maximization of Non-Submodular Objectives

Volkan Cevher, Ilija Bogunovic, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exi ...

2018

Content Based Status Updates

Emre Telatar, Elie Najm, Rajai Nasser

Consider a stream of status updates generated by a source, where each update is of one of two types: priority or ordinary; these updates are to be transmitted through a network to a monitor. We analyze a transmission policy that treats updates depending on ...

2018

Content Based Status Updates

Emre Telatar, Elie Najm, Rajai Nasser

Consider a stream of status updates generated by a source, where each update is of one of two types: priority or ordinary; these updates are to be transmitted through a network to a monitor. We analyze a transmission policy that treats updates depending on ...

IEEE2018

Extension complexity of stable set polytopes of bipartite graphs

Yuri Faenza, Manuel Francesco Aprile

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

Springer2017

On sums of eigenvalues of elliptic operators on manifolds

Joachim Stubbe

We use the averaged variational principle introduced in a recent article on graph spectra [10] to obtain upper bounds for sums of eigenvalues of several partial differential operators of interest in geometric analysis, which are analogues of Kroger's bound ...

European Mathematical Soc2017

Ambiguous Joint Chance Constraints under Mean and Dispersion Information

Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann

We study joint chance constraints where the distribution of the uncertain parameters is only known to belong to an ambiguity set characterized by the mean and support of the uncertainties and by an upper bound on their dispersion. This setting gives rise t ...

Informs2017

Rich Vehicle and Inventory Routing Problems with Stochastic Demands

Iliya Dimitrov Markov

This thesis develops a unified framework for modeling and solving various classes of rich routing problems with stochastic demands, including the VRP and the IRP. The work is inspired by the problem of collecting recyclables from sensorized containers in G ...

EPFL2017

A feasible-side globally convergent modifier-adaptation scheme

Dominique Bonvin, Timm Faulwasser, Alejandro Gabriel Marchetti

In the context of static real-time optimization (RTO) of uncertain plants, the standard modifier-adaptation scheme consists in adding first-order correction terms to the cost and constraint functions of a model based optimization problem. If the algorithm ...

Elsevier Sci Ltd2017

Upper and lower bounds

Graph Chatbot

Chat with Graph Search

Decision Rule Bounds for Two-Stage Stochastic Bilevel Programs

epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

Robust Maximization of Non-Submodular Objectives

Content Based Status Updates

Content Based Status Updates

Extension complexity of stable set polytopes of bipartite graphs

On sums of eigenvalues of elliptic operators on manifolds

Ambiguous Joint Chance Constraints under Mean and Dispersion Information

Rich Vehicle and Inventory Routing Problems with Stochastic Demands

A feasible-side globally convergent modifier-adaptation scheme

Decision Rule Bounds for Two-Stage Stochastic Bilevel Programs

On sums of eigenvalues of elliptic operators on manifolds

epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

Robust Maximization of Non-Submodular Objectives

Content Based Status Updates

Extension complexity of stable set polytopes of bipartite graphs

Ambiguous Joint Chance Constraints under Mean and Dispersion Information

Content Based Status Updates

Rich Vehicle and Inventory Routing Problems with Stochastic Demands

A feasible-side globally convergent modifier-adaptation scheme