Optimal Rounding of Instantaneous Fractional Flows Over Time (2007)
Lisa K. Fleischer, James B. Orlin
A transshipment problem with demands that exceed network capacity can be solved by sending ow inseveral waves. How can this be done in the minimum number, T,ofwaves, and at minimum cost, if costs are...
Lisa K. Fleischer, Bruce Hendrickson, I Pinar
Abstract. The standard serial algorithm for strongly connected components has linear complexity and is based on depth first search. Unfortunately, depth first search is difficult to parallelize. We...
Polynomial-time separation of a superclass of simple comb inequalities (2006)
Lisa K. Fleischer, Adam N. Letchford, Andrea Lodi
The comb inequalities are a well-known class of facet-inducing inequalities for the Traveling Salesman Problem, defined in terms of certain vertex sets called the handle and the teeth. We say that a...
Polynomial-time separation of a superclass of simple comb inequalities (2006)
Lisa K. Fleischer, Adam N. Letchford, Andrea Lodiffi
Abstract The comb inequalities are a well-known class of facet-inducing inequalities for the Traveling Salesman Problem, defined in terms of certain vertex sets called the handle and the teeth. We...
A Fast Approximation Scheme for Fractional Covering Problems with Box Constraints (2004)
We present the first combinatorial approximation scheme that yields a pure approximation guarantee for linear programs that are either covering problems with upper bounds on variables, or their...
Further improvements in competitive guarantees for QoS buffering (2004)
Nikhil Bansal, Lisa K Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko
Abstract. We study the behavior of algorithms for buffering packets weighted by different levels of Quality of Service (QoS) guarantees in a single queue. Buffer space is limited, and packet loss...
Quickest flows over time (2003)
Lisa K. Fleischer, Lisa Fleischer, Martin Skutella, Martin Skutella
LIMITED DISTRIBUTION NOTICE: This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research
Approximately Optimal control of Fluid Networks (2003)
Lisa K. Fleischer, Lisa Fleischer, Jay Sethuraman, Jay Sethuraman
Abstract. We give an approximation algorithm for the optimal control problem in fluid networks. Such problems arise as fluid relaxations of multiclass queueing networks, and are used to find...
Fast and simple approximation schemes for generalized flow (2001)
Lisa K. Fleischer, Kevin D. Wayne
We present fast and simple fully...
Fast and Simple Approximation Schemes for Generalized Flow (2001)
Lisa K. Fleischer, Kevin D. Wayne
We present fast and simple fully polynomial-time approximation schemes (FPTAS) for generalized versions of maximum flow, multicommodity flow, minimum cost maximum flow, and minimum cost...
On Identifying Strongly Connected Components in Parallel (2000)
Lisa K. Fleischer, Bruce Hendrickson, Ali Pinar
. The standard serial algorithm for strongly connected components is based on depth first search, which is difficult to parallelize. We describe a divide-and-conquer algorithm for this problem which...
Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems (2000)
Robert D. Carr, Lisa K. Fleischer, Vitus J. Leung, Cynthia A. Phillips
A capacitated covering IP is an integer program of the form minfcxjUx d; 0 x b; x 2 Z + g, where all entries of c, U , and d are nonnegative. Given such a formulation, the ratio between the optimal...
Approximating fractional multicommodity flow independent of the number of commodities (2000)
Abstract. We describe fully polynomial time approximation schemes for various multicommodity flow problems in graphs with m edges and n vertices. We present the first approximation scheme for maximum...
On identifying strongly connected components in parallel (2000)
Lisa K. Fleischer, Bruce Hendrickson, Ali P Nar
Abstract. The standard serial algorithm for strongly connected components is based on depth rst search, which is di cult to parallelize. We describe a divide-and-conquer algorithm for this problem...
Approximating Fractional Multicommodity Flow Independent of the Number of Commodities (1999)
We describe fully polynomial time approximation schemes for various multicommodity flow problems in graphs with m edges and n vertices. We present the first approximation scheme for maximum...
OF TECHNOLOG Y Optimal Rounding of Instantaneous Fractional Flows Over Time (1999)
Lisa K. Fleischer, James B. Orlin
A transshipment problem with demands that exceed network capacity can be solved by sending flow in several waves. How can this be done in the minimum number, T, of waves, and at minimum cost, if...