Amar S. Gupta Chair for Decision Sciences
About	Seminars	Teaching	Research
Jan 17, 2013	4pm	Seminar Room, CSE
Integrated Optimization of Customer and Supplier Logistics at Robert Bosch LLC
R. Ravi Carnegie Bosch Professor of Operations Research and Computer Science, Tepper School of Business, Carnegie Mellon University.
Large automotive supply chain typically involve manufacturers pulling materials using their logistics divisions from their suppliers along the chain. However, the cost structure of round-trip full-truckloads versus less-than-truckloads often results in round-trip milkruns for pulling materials from suppliers whose return trips are under utilized. A simple MIP model can be formulated to identify a subset of the most promising customer routes that can be combined with the existing supplier milkruns to save the overall costs of the system. Such an integration also leads to other supply-chain coordination benefits such as the potential of using crossdocks, more frequent milkruns and ensuing reductions in inventories. We undertake such an integrated study of the inbound logistics from suppliers and the outbound logistics to customers at Robert Bosch LLC, a leading automotive parts manufacturer. We identify the opportunity for significant cost savings over the current system by matching opposite flows of material from and to the customers and suppliers. We consider the problem from a supply chain coordination perspective, where Bosch makes all the transportation arrangements for its customers and suppliers based on the results of the centralized optimum solution, and outline its additional benefits. Joint work with Hakan Yildiz, Eli Broad College of Business, Michigan State University, and Wayne Fairey, Customer Service, Logistics & Planning (ChP/CLP), Robert Bosch LLC, Charleston.
Dec 17, 2013	4pm	Seminar Room, CSE
Market Equilibrium: Complementary Pivot Algorithms and How they Led to a New Class of Utility Functions
Vijay V. Vazirani Professor College of Computing Georgia Institute of Technology
Market equilibrium is an inherently algorithmic notion  -- this should be obvious from the fact that Walras, who while defining this notion in 1874, also gave a mechanism for arriving at an equilibrium, namely the tatonnement process.  In the 1970s, attention shifted to centralized algorithms and impressive approaches were given by Scarf and Smale; however, these algorithms were slow, and moreover they suffered from issues of numerical instability. In 1974, Eaves gave a complementary pivot algorithm for the linear case of the Arrow-Debreu market model. Although this approach was far superior, since complementary pivot algorithms tend to be very fast in practice and do not suffer from issues of numerical instability, it was not extended to more general utility functions until two years ago. We will summarize the new developments, which led to complementary pivot algorithms for separable, piecewise-linear concave (SPLC) utility functions and SPLC production sets. Recently, they also led to the definition of a new class of utility functions, called Leontief-free, which are applicable when goods are substitutes, e.g., bread and bagels. We note that when goods are complements, e.g., bread and butter, the classical Leontief function does a splendid job. Surprisingly enough, for the former case, utility functions had been defined only for special cases in economics, e.g., CES utility function. A new min-max relation supports the claim that our notion is well-founded. This talk is fully self-contained. It is designed for researchers in TCS and mathematical economics. It is based on joint works with Jugal Garg and Ruta Mehta, in particular: http://www.cc.gatech.edu/~vazirani/LF.pdf
Feb 20, 2014	4pm	Committee Room, CSE
A Mazing 2+eps Approximation for Unsplittable Flow on a Path
Fabrizio Grandoni Senior Researcher IDSIA Manno, Switzerland
We study the unsplittable flow on a path problem (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with nonnegative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly, this problem has received a lot of attention in the research community. If the demand of each task is at most a small enough fraction delta of the capacity along its subpath (delta-small tasks), then it has been known for a long time [Chekuri et al., ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction delta>0 of the smallest capacity of its subpath (delta-large tasks). For this setting a constant factor approximation, improving on an earlier logarithmic approximation, was found only recently [Bonsma et al., FOCS 2011]. In this paper we present a PTAS for delta-large tasks, for any constant delta>0. Key to this result is a complex geometrically inspired dynamic program. Each task is represented as a segment underneath the capacity curve, and we identify a proper maze-like structure so that each corridor of the maze is crossed by only O(1) tasks in the optimal solution. The maze has a tree topology, which guides our dynamic program. Our result implies a 2+eps approximation for UFP, for any constant eps>0, improving on the previously best 7+eps approximation by Bonsma et al. We remark that our improved approximation algorithm matches the best known approximation ratio for the considerably easier special case of uniform edge capacities. (joint work with A. Anagnostopoulos, S. Leonardi, and A. Wiese)
Feb 3, 2015	12noon	Seminar Room, CSE
Online bin packing: Old algorithms and new results
Jiri Sgall Professor Computer Science Institute of Charles University  Praha, Czech Republic
In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit and BestFit algorithms are simple online algorithms introduced in early seventies, when it was also shown that their asymptotic approximation ratio is equal to 1.7.  We survey recent developments that lead to the proof that also the absolute approximation ratio of these algorithms is exactly 1.7 and an online algorithm with the optimal absolute ratio of 5/3.