Organizing Committee
Abstract

Combinatorial optimization is an active research field in mathematics, with an immense range of applications. This workshop will bring together researchers and leading experts interested in the mathematical foundations of combinatorial optimization algorithms to discuss new tools and methods, in particular regarding the use of algebraic, analytical, and geometric techniques. Special emphasis will be given on polyhedral methods, since they are at the core of several groundbreaking combinatorial optimization results developed in recent years.

Image for "Combinatorics and Optimization"

Confirmed Speakers & Participants

Talks will be presented virtually or in-person as indicated in the schedule below.

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, March 27, 2023
  • 8:30 - 8:50 am EDT
    Check In
    11th Floor Collaborative Space
  • 8:50 - 9:00 am EDT
    Welcome
    11th Floor Lecture Hall
    • Brendan Hassett, ICERM/Brown University
  • 9:00 - 9:45 am EDT
    Interior point methods are not worse than Simplex
    11th Floor Lecture Hall
    • Speaker
    • Daniel Dadush, Centrum Wiskunde & Informatica
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the classical simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.

    The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of n shadow vertex simplex paths.

    This is joint work with Xavier Allamigeon (INRIA / Ecole Polytechnique), Georg Loho (U. Twente), Bento Natura (LSE), Laszlo Vegh (LSE).
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Partitioning over submodular structures
    11th Floor Lecture Hall
    • Speaker
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    In submodular k-partitioning problems, the input is a submodular set function (given via an evaluation oracle) along with a fixed positive integer k (e.g., k = 2, 3, 4, …) and the goal is to partition the ground set into k non-empty parts so as to minimize certain natural objectives of interest. Submodular k-partitioning generalizes partitioning problems over several interesting structures including graphs and hypergraphs. The case of 2-partitioning corresponds to the classic and well-studied submodular minimization problem which is polynomial-time solvable. In this talk, I will outline recent progress towards polynomial-time solvability of submodular k-partitioning for fixed constant integers k >= 3.
  • 11:30 am - 12:15 pm EDT
    The Polyhedral Structure of Graphical Designs
    11th Floor Lecture Hall
    • Speaker
    • Catherine Babecki, University of Washington, Seattle
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    A graphical design is a quadrature rule for a graph inspired by classical numerical integration on the sphere. Broadly speaking, that means a graphical design is a relatively small subset of graph vertices chosen to capture the global behavior of functions from the vertex set to the real numbers. We first motivate and define graphical designs for graphs with positive edge weights. Through Gale duality, we exhibit a combinatorial bijection between graphical designs and the faces of certain polytopes associated to a graph, called eigenpolytopes. This polytope connection has a variety of beautiful consequences, including a proof of existence, an upper bound on the cardinality of a graphical design, methods to compute, optimize, and organize graphical designs, the existence of random walks with improved convergence rates, and complexity results for associated computational problems. This talk is based on work with Rekha Thomas, Stefan Steinerberger and David Shiroma.
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
  • 2:30 - 3:15 pm EDT
    Two New Algorithms for Set Covering
    11th Floor Lecture Hall
    • Speaker
    • Anupam Gupta, Carnegie Mellon University
    • Session Chair
    • Yuri Faenza, Columbia University
    Abstract
    In the set covering problem we are given a set system, and we want to find a subcollection with few sets whose union is the entire universe. This problem is NP-hard to approximate to better than (ln n). Moreover we know matching algorithms which are achieved by both greedy and relax-and-round based algorithms. In this talk I will give two more algorithms which achieve the same guarantee (asymptotically), one based on local search, and another based on a learning-based framework (which also works in an online setting with random arrivals). These results are based on joint works with Greg Kehne, Euiwoong Lee, Roie Levin, and Jason Li.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Alternating Linear Minimization: Revisiting von Neumann’s alternating projections
    11th Floor Lecture Hall
    • Speaker
    • Sebastian Pokutta, Zuse Institute Berlin (ZIB)
    • Session Chair
    • Yuri Faenza, Columbia University
    Abstract
    In 1933 von Neumann proved a beautiful result that one can compute a point in the intersection of two convex sets (under suitable assumptions) by alternating projections, i.e., successively projecting on one set and then the other. This algorithm assumes that one has access to projection operators for both sets. Here we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets. Moreover, we provide a modification of the algorithm to minimize a linear function over the intersection and discuss further extensions.
  • 5:00 - 6:30 pm EDT
    Reception
    11th Floor Collaborative Space
Tuesday, March 28, 2023
  • 9:00 - 9:45 am EDT
    Reusing Cuts in Iterative Projections over Submodular Polytopes
    11th Floor Lecture Hall
    • Speaker
    • Swati Gupta, Georgia Tech
    • Session Chair
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
    Abstract
    Optimization algorithms such as projected Newton's method, FISTA, mirror descent and its variants enjoy near-optimal regret bounds and convergence rates, but suffer from a computational bottleneck of computing projections"" in potentially each iteration (e.g., O(T^{0.5}) regret of online mirror descent). On the other hand, conditional gradient variants solve a linear optimization in each iteration, but result in suboptimal rates (e.g., OT^{0.75}) regret of online Frank-Wolfe). Motivated by this trade-off in runtime v/s convergence rates, we consider iterative projections of close-by points over widely-prevalent submodular base polytopes B(f). We develop a toolkit to speed up the computation of projections using both discrete and continuous perspectives. We subsequently adapt the away-step Frank-Wolfe algorithm to use this information and enable early termination.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Clique Trees and Disjunctive Constraints
    11th Floor Lecture Hall
    • Speaker
    • Illya Hicks, Rice University
    • Session Chair
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
    Abstract
    In this talk, we explore the concept of combinatorial disjunctive constraints (CDC) and their properties. In particular, we examine when one can build small ideal mixed-integer programming (MIP) formulations using CDCs and their linkages to clique trees. We also show that generalized special ordered sets (SOS k) can be modeled by CDCs with ties to clique trees.
  • 11:30 am - 12:15 pm EDT
    Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
    11th Floor Lecture Hall
    • Speaker
    • Stefan Weltge, Technical University of Munich
    • Session Chair
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
    Abstract
    Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give an explicit family of stable set polytopes of n-node graphs for which every polynomial-size formulation requires Ω(n / log^2 n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack polytopes. This improves the previously known bounds of Ω(√n / log n) by Cevallos, Weltge & Zenklusen (SODA 2018). To this end, we extend a result of Göös, Jain & Watson (FOCS 2016, SIAM J. Comput. 2018) showing that the linear extension complexity of stable set polytopes of some n-node graphs is 2^(Ω(n / log n)). We show that the same bound holds for ɛ/n-approximations of these polytopes, for some constant ɛ > 0. On this way, we simplify several of their original arguments to obtain a proof that is accessible to a broader community. For instance, our proof does not require reductions to certain CSP problems or the notion of Karchmer-Wigderson games. This is joint work with Jamico Schade and Makrand Sinha.
  • 12:30 - 2:00 pm EDT
    Networking Lunch
    Lunch/Free Time - 11th Floor Collaborative Space
  • 2:00 - 2:45 pm EDT
    Arc connectivity and submodular flows in digraphs
    11th Floor Lecture Hall
    • Speaker
    • Ahmad Abdi, London School of Economics
    • Session Chair
    • Steffen Borgwardt, University of Colorado Denver
    Abstract
    Given a digraph D, and an integer k>=1, a k-arc-connected flip is an arc subset whose reversal makes the digraph (strongly) k-arc-connected. The main result of this work introduces a sufficient condition for the existence of a k-arc-connected flip that is also a submodular flow for a crossing submodular function. The main result has several applications to graph orientations and combinatorial optimization. For instance, if the underlying graph of D is t-edge-connected for some integer t>=2, there exists a decomposition of the arc set into a k-arc-connected flip and a (t-k)-dijoin, for any integer k such that 1<=k<=t/2. This extends Nash-Williams’ weak orientation theorem, as well as proves a weaker variant of Woodall’s conjecture on such digraphs. The main result follows from a surprising sufficient condition for the existence of capacitated integral solutions to the intersection of two submodular flow systems. This result in turn has some applications for submodular optimization. For instance, in a weakly connected digraph, the intersection of two submodular flow systems defines an integral polyhedron. Joint work with Gerard Cornuejols and Giacomo Zambelli.
  • 3:00 - 3:45 pm EDT
    Smoothed Analysis of the Simplex Method
    11th Floor Lecture Hall
    • Speaker
    • Sophie Huiberts, Columbia University
    • Session Chair
    • Steffen Borgwardt, University of Colorado Denver
    Abstract
    Explaining why the simplex method is fast in practice, despite it taking exponential time in the theoretical worst case, continues to be a challenge. Smoothed analysis is a paradigm for addressing this question. During my talk I will present recent progress in the smoothed complexity of the simplex method, discussing both upper and lower bounds.
  • 4:00 - 4:30 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:30 - 6:00 pm EDT
    Poster Session
    10th Floor Collaborative Space
Wednesday, March 29, 2023
  • 9:00 - 9:45 am EDT
    Degree Sequence Optimization and Sparse Integer Programming
    11th Floor Lecture Hall
    • Speaker
    • Shmuel Onn, Technion - Israel Institute of Technology
    • Session Chair
    • Antoine Deza, McMaster University
    Abstract
    I will suggest several open problems on optimization over degree sequences of graphs and hypergraphs and over line sums of matrices; describe several recent partial results such as for convex functions, complete graphs, complete bipartite graphs and monotone matrices, and bounded tree width or depth; and outline some proof techniques, including our recent powerful theory of sparse integer programming in high dimensions, which will be explained.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Algorithmic, combinatorial, and geometric aspects of linear optimization
    11th Floor Lecture Hall
    • Speaker
    • Lionel Pournin, University of Paris 13
    • Session Chair
    • Antoine Deza, McMaster University
    Abstract
    The simplex and interior point methods are currently the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. The complexity of these methods is closely related to the combinatorial and geometric structures of the feasible region. Focusing on the analysis of worst-case constructions leading to computationally challenging instances, recently obtained lower bounds on the largest possible diameter of lattice polytopes will be presented. These bounds, via lattice zonotopes, are established using tools from combinatorics and number theory. This talk is based on joint work with Antoine Deza.
  • 11:30 am - 12:15 pm EDT
    The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
    11th Floor Lecture Hall
    • Speaker
    • Ola Svensson, EPFL
    • Session Chair
    • Antoine Deza, McMaster University
    Abstract
    Given a graph with edges colored red or blue and an integer k, the exact perfect matching problem asks if there exists a perfect matching with exactly k red edges. There exists a randomized polylogarithmic-time parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomial-time algorithm is known, even for bipartite graphs. In this talk, we discuss known approaches and their limitations. In particular, we show that there is no sub-exponential-sized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no sub-exponential-sized linear program to describe the convex hull of perfect matchings with an odd number of red edges. To prove our result, we devise an exponential set of valid constraints that we believe are interesting in their own right. In particular, we leave as an open problem whether they define the convex hull of perfect matchings with an odd number of red edges.

    This is joint work with Xinrui Jia and Weiqiang Yuan
  • 12:15 - 12:30 pm EDT
    Group Photo (Immediately After Talk)
    11th Floor Lecture Hall
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
  • 2:30 - 3:15 pm EDT
    Approximating Weighted Connectivity Augmentation Below Factor 2
    11th Floor Lecture Hall
    • Speaker
    • Rico Zenklusen, ETH Zurich
    • Session Chair
    • Sophie Huiberts, Columbia University
    Abstract
    The Weighted Connectivity Augmentation Problem (WCAP) asks to augment the edge-connectivity of a graph by adding a min cost edge set among given candidate edges. It is among the most elementary network design problems for which no better-than-2 approximation has been known, whereas 2-approximations can easily be obtained through a variety of well-known techniques. In this talk, I will discuss an approach showing that approximation factors below 2 are achievable for WCAP, ultimately leading to a (1.5+epsilon)-approximation. Our approach is based on a highly structured directed simplification of WCAP with planar optimal solutions. We show how one can successively improve solutions of this directed simplification by moving to mixed solutions, consisting of both directed and undirected edges. These insights can be leveraged in local search and relative greedy strategies, inspired by recent advances on the Weighted Tree Augmentation Problem, to obtain a (1.5+epsilon)-approximation. This is joint work with Vera Traub.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Unit and distinct distances in typical norms
    11th Floor Lecture Hall
    • Speaker
    • Lisa Sauermann, MIT
    • Session Chair
    • Sophie Huiberts, Columbia University
    Abstract
    Given n points in the plane, how many pairs among these points can have distance exactly 1? More formally, what is the maximum possible number of unit distances among a set of n points in the plane? This problem is a very famous and still largely open problem, called the Erdos unit distance problem. One can also study this problem for other norms on R^2 (or more generally on R^d for any dimension d) that are different from the Euclidean norm. This direction has been suggested in the 1980s by Ulam and Erdos and attracted a lot of attention over the years. We give an almost tight answer to this question for almost all norms on R^d (for any given d). Furthermore, for almost all norms on R^d, we prove an asymptotically tight bound for a related problem, the so-called Erdos distinct distances problem. Our proofs rely in part on arguments from polyhedral geometry (and some tools from matroid theory are also relevant). Joint work with Noga Alon and Matija Bucic.
Thursday, March 30, 2023
  • 9:00 - 9:45 am EDT
    Understanding graphs locally
    11th Floor Lecture Hall
    • Speaker
    • Annie Raymond, University of Massachusetts, Amherst
    • Session Chair
    • Mohit Singh, Georgia Tech
    Abstract
    Graphs are ubiquitous in modern applications---including some very large graphs. This leads one to wonder, "How can we understand such large graphs?" One prevalent idea is to observe them locally: to count how many times certain substructures appear. If one knows something about the number of some particular substructures in a graph, what can one say about the number of other substructures or about global properties of the graph in general? Such problems are at the heart of extremal graph theory. In this talk, we will discuss successes and challenges in proving inequalities involving these substructures. We will also encounter graph profiles, complicated objects that allow us to understand all polynomial inequalities involving some fixed set of substructures. This is joint work with Greg Blekherman, Mohit Singh, Rekha Thomas and Fan Wei.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Untangling near minimum cuts with applications in network design
    11th Floor Lecture Hall
    • Speaker
    • Nathan Klein, University of Washington
    • Session Chair
    • Mohit Singh, Georgia Tech
    Abstract
    The structure of the set of global minimum cuts of a graph is well understood and is captured by a cactus, as proved by Dinitz, Karzanov, and Lomonosov in the 70s. However, even for small epsilon, the set of (1+epsilon) near minimum cuts has a significantly more complex structure. Benczúr and Goemans studied near minimum cuts starting in the late 90s and showed that they admit a so-called polygon representation. In this talk I will show new algorithmically useful properties of this representation and demonstrate two applications in approximating network design problems.
  • 11:30 am - 12:15 pm EDT
    The Subspace Flatness Conjecture and Faster Integer Programming
    11th Floor Lecture Hall
    • Speaker
    • Thomas Rothvoss, University of Washington
    • Session Chair
    • Mohit Singh, Georgia Tech
    Abstract
    In a seminal paper, Kannan and Lov\'asz (1988) considered a quantity $\mu_{KL}(\Lambda,K)$ which denotes the best volume-based lower bound on the covering radius $\mu(\Lambda,K)$ of a convex body $K$ with respect to a lattice $\Lambda$. Kannan and Lov\'asz proved that $\mu(\Lambda,K) \leq n \cdot \mu_{KL}(\Lambda,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log n)$ factor suffices, which would match the lower bound from the work of Kannan and Lov\'asz. We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda,K) \leq O(\log^{7}(n)) \cdot \mu_{KL} (\Lambda,K)$. Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a $(\log n)^{O(n)}$-time randomized algorithm to solve integer programs in $n$ variables. Another implication of our main result is a near-optimal flatness constant of $O(n \log^{8}(n))$. This is joint work with Victor Reis.
  • 12:30 - 2:30 pm EDT
    Networking Lunch
    Lunch/Free Time - 11th Floor Collaborative Space
  • 2:30 - 3:15 pm EDT
    Transshipments over time, submodular functions, and discrete Newton
    11th Floor Lecture Hall
    • Speaker
    • Martin Skutella, TU Berlin
    • Session Chair
    • Annie Raymond, University of Massachusetts, Amherst
    Abstract
    The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental importance for numerous applications in areas such as logistics, traffic, evacuation, and finance. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for this problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running time, is hardly practical as it relies on parametric submodular function minimization via Megiddo's parametric search. We present considerably faster algorithms for the Quickest Transshipment Problem that instead employ a subtle extension of the Discrete Newton Method. This improves the previously best known running time of $\tilde{O}(m^4k^{14})$ to $\tilde O(m^2k^5+m^3k^3+m^3n)$, where $n$ is the number of nodes, $m$ the number of arcs, and $k$ the number of source and sink nodes. Furthermore, we show how to compute integral quickest transshipments in $\tilde O(m^2k^6+m^3k^4+m^3n)$ time.

    This is joint work with Miriam Schlöter and Khai Van Tran.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Openly Disjoint Paths, Jump Systems, and Discrete Convexity
    11th Floor Lecture Hall
    • Speaker
    • Satoru Iwata, University of Tokyo
    • Session Chair
    • Annie Raymond, University of Massachusetts, Amherst
    Abstract
    In 1978, Mader discovered a min-max theorem on the number of openly disjoint paths between terminals. Sadli and Sebo (2000) showed that the set of integer vectors in that appear as degree sequences of openly disjoint paths forms a jump system. In this talk, we describe an alternative proof of this fact by using a reduction to matroid matching, which was originally observed by Lovasz (1980). In addition, we show that a function on this jump system determined by the minimum total length of openly disjoint paths enjoys the M-convexity introduced by Murota (2006).
Friday, March 31, 2023
  • 9:00 - 9:45 am EDT
    Thin trees for laminar families
    11th Floor Lecture Hall
    • Speaker
    • Neil Olver, London School of Economics
    • Session Chair
    • Britta Peis, RWTH Aachen University
    Abstract
    In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This conjecture, if true, has a variety of implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Via a simple reduction technique followed by iterative relaxation, we show that the thin tree conjecture is true for laminar families of cuts, resolving an open question of Olver and Zenklusen from 2013. Joint work with Nathan Klein.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Streaming algorithms for k-submodular maximization and ad allocation
    11th Floor Lecture Hall
    • Speaker
    • Alina Ene, Boston University
    • Session Chair
    • Britta Peis, RWTH Aachen University
    Abstract
    Maximizing a monotone k-submodular function subject to cardinality constraints is a general model for several applications ranging from influence maximization with multiple products to sensor placement with multiple sensor types and online ad allocation. Due to the large problem scale in many applications and the online nature of ad allocation, a need arises for algorithms that process elements in a streaming fashion and possibly make online decisions. In this talk, we present a streaming algorithm for maximizing a monotone k-submodular function subject to a per-coordinate cardinality constraint attaining an approximation guarantee close to the state of the art guarantee in the offline setting. We also give a variant of the algorithm that is able to leverage machine learning predictions.
  • 11:30 am - 12:15 pm EDT
    Non-Adaptive Matroid Prophet Inequalities
    11th Floor Lecture Hall
    • Speaker
    • Kanstantsin Pashkovich, University of Waterloo
    • Session Chair
    • Britta Peis, RWTH Aachen University
    Abstract
    We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight 2-competitive mechanism for all matroids. However, it is not known what classes of matroids admit non-adaptive mechanisms with constant guarantee. Recently, it was shown that there are constant-competitive non-adaptive mechanisms for graphic matroids. In this talk, we show that various known classes of matroids admit constant-competitive non-adaptive mechanisms.
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
  • 2:30 - 3:15 pm EDT
    Approximating Nash Social Welfare for Submodular Valuations
    11th Floor Lecture Hall
    • Speaker
    • László Végh, London School of Economics
    • Session Chair
    • Gerard Cornuejols, Carnegie Mellon University
    Abstract
    The Nash social welfare (NSW) problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents’ valuations. This is a common objective for fair division, representing a balanced tradeoff between the often conflicting requirements of fairness and efficiency. The problem is NP-complete already for additive valuation functions. We present a simple, deterministic 4-approximation algorithm for the Nash Social Welfare problem under the general class submodular valuation functions. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem where the objective is to maximize the weighted geometric mean of agents’ valuations, and give a (α+2)e-approximation, where α is the ratio between largest weight and the average weight. This is joint work with Jugal Garg, Edin Husić, Wenzheng Li, and Jan Vondrák.
  • 3:30 - 4:15 pm EDT
    Optimal Deployment of Electric Vehicle Charging Infrastructure via Bilevel Optimization
    11th Floor Lecture Hall
    • Speaker
    • Miguel Anjos, University of Edinburgh
    • Session Chair
    • Gerard Cornuejols, Carnegie Mellon University
    Abstract
    The increase of electric vehicle (EV) adoption in recent years has correspondingly increased the importance of providing adequate charging infrastructure for EV users. For a charging service provider, the fundamental question is to determine the optimal location and sizing of charging stations with respect to a given objective and subject to budget and other practical constraints. One possible objective is to maximize EV adoption as part of a public policy on electric transportation. Alternatively, the objective may be to maximize the profit gained from providing this service, in which case the price of charging is also to be optimized. These problems are fundamentally combinatorial and frequently formulated using mixed-integer linear optimization. In this talk, the focus will be on the use of bilevel optimization in this area, in particular to more accurately capture the interactions between the charging service provider and the EV users.
  • 4:30 - 5:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space

All event times are listed in ICERM local time in Providence, RI (Eastern Daylight Time / UTC-4).

All event times are listed in .

Request Reimbursement

This section is for general purposes only and does not indicate that all attendees receive funding. Please refer to your personalized invitation to review your offer.

ORCID iD
As this program is funded by the National Science Foundation (NSF), ICERM is required to collect your ORCID iD if you are receiving funding to attend this program. Be sure to add your ORCID iD to your Cube profile as soon as possible to avoid delaying your reimbursement.
Acceptable Costs
  • 1 roundtrip between your home institute and ICERM
  • Flights on U.S. or E.U. airlines – economy class to either Providence airport (PVD) or Boston airport (BOS)
  • Ground Transportation to and from airports and ICERM.
Unacceptable Costs
  • Flights on non-U.S. or non-E.U. airlines
  • Flights on U.K. airlines
  • Seats in economy plus, business class, or first class
  • Change ticket fees of any kind
  • Multi-use bus passes
  • Meals or incidentals
Advance Approval Required
  • Personal car travel to ICERM from outside New England
  • Multiple-destination plane ticket; does not include layovers to reach ICERM
  • Arriving or departing from ICERM more than a day before or day after the program
  • Multiple trips to ICERM
  • Rental car to/from ICERM
  • Flights on a Swiss, Japanese, or Australian airlines
  • Arriving or departing from airport other than PVD/BOS or home institution's local airport
  • 2 one-way plane tickets to create a roundtrip (often purchased from Expedia, Orbitz, etc.)
Travel Maximum Contributions
  • New England: $250
  • Other contiguous US: $750
  • Asia & Oceania: $2,000
  • All other locations: $1,500
  • Note these rates were updated in Spring 2022 and superseded any prior invitation rates. Any invitations without travel support will still not receive travel support.
Reimbursement Requests

Request Reimbursement with Cube

Refer to the back of your ID badge for more information. Checklists are available at the front desk and in the Reimbursement section of Cube.

Reimbursement Tips
  • Scanned original receipts are required for all expenses
  • Airfare receipt must show full itinerary and payment
  • ICERM does not offer per diem or meal reimbursement
  • Allowable mileage is reimbursed at prevailing IRS Business Rate and trip documented via pdf of Google Maps result
  • Keep all documentation until you receive your reimbursement!
Reimbursement Timing

6 - 8 weeks after all documentation is sent to ICERM. All reimbursement requests are reviewed by numerous central offices at Brown who may request additional documentation.

Reimbursement Deadline

Submissions must be received within 30 days of ICERM departure to avoid applicable taxes. Submissions after thirty days will incur applicable taxes. No submissions are accepted more than six months after the program end.

Associated Semester Workshops

Linear and Non-Linear Mixed Integer Optimization
Image for "Linear and Non-Linear Mixed Integer Optimization"
Trends in Computational Discrete Optimization
Image for "Trends in Computational Discrete Optimization"