Submodular approximation: sampling-based algorithms and lower bounds (2008)
Svitkina, Zoya, Fleischer, Lisa
We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular...
Iterative Rounding 2-Approximation Algorithms (2004)
Lisa Fleischer, Kamal Jain, David P. Williamson
The survivable network design problem (SNDP) is the following problem: given an undirected graph and values r ij for each pair of vertices i and j, find a minimum-cost subgraph such that there are r...
Quickest Flows Over Time (2003)
Lisa Fleischer, Martin Skutella
Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous....
A divide-and-conquer algorithm for identifying strongly connected components (2003)
Coppersmith, Don, Fleischer, Lisa, Hendrickson, Bruce, Pinar, Ali
Strongly connected components of a directed graph can be found in an optimal linear time, by algorithms based on depth first search. Unfortunately, depth first search is difficult to parallelize. We...
Sensor Placement in Municipal Water Networks (2003)
Jonathan Berry, Lisa Fleischer, William Hart, Cynthia Phillips
We present a model for optimizing the placement of sensors in municipal water networks to detect maliciously-injected contaminants. An optimal sensor configuration minimizes the expected fraction of...
Minimum Cost Flows Over Time without Intermediate Storage (2003)
Lisa Fleischer, Martin Skutella
Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous....
Minimum Cost Flows Over Time without Intermediate Storage (2003)
Fleischer,Lisa, Skutella,Martin
Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous....
Minimum Cost Flows Over Time without Intermediate Storage (2003)
Fleischer, Lisa, Skutella, Martin
Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous....
The Quickest Multicommodity Flow Problem (2002)
Traditionally, ows over time are solved in time-expanded networks which contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic...
Improved Algorithms for Submodular Function Minimization and Submodular Flow (2001)
Very recently, two groups of researchers independently developed the first combinatorial, strongly polynomial-time al- gorithms for submodular function minimization (Iwata, Flei- scher, Fujishige;...
Recently, the first combinatorial strongly polynomial algorithms for submodular function minimization have been devised independently by Iwata, Fleischer, and Fujishige and by Schrijver. In this...
An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem (2001)
Lisa Fleischer, Kamal Jain, David P. Williamson
In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. Jain et al....
A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow (2001)
Lisa Fleischer, Satoru Iwata, S. Thomas Mccormick
We describe an O(a4h minilog U, a2 log a)) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds-Karp capacity scaling algorithm for...
A 2-approximation for Minimum Cost {0, 1, 2} Vertex Connectivity (2001)
In survivable network design, each pair (i,j) of vertices is assigned a level of importance vii. The vertex connectivity problem is to design a minimum cost network such that between each pair of...
Near-Optimal Design of MPS Tunnels with (2001)
Lisa Fleischer, Adam Meyerson, Iraj Saniee, Bruce Shepherd, Aravind Srinivasan
We describe the optimization problem associated with the concurrent routing of demands with guaranteed shared recovery in case of network failures. This problem arises in routing with protection in...
Recent Progress in Submodular Function Minimization (2000)
This article is an attempt to relate the history and importance of the problem, the difficulties that arose in confronting it, the motivation for the solutions proposed, some consequences of the...
A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions (2000)
Satoru Iwata, Lisa Fleischer, Satoru Fujishige
This paper presents the first combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lovász, and Schrijver. The...
A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions (2000)
Iwata, Satoru, Fleischer, Lisa, Fujishige, Satoru
This paper presents the first combinatorial polynomial-time algorithm for minimizing submodular set functions, answering an open question posed in 1981 by Grotschel, Lovasz, and Schrijver. The...
A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow (1999)
Lisa Fleischer, Satoru Iwata, S. Thomas Mccormick
We describe an O(n 4 h minflog U; n 2 log ng) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds--Karp capacity scaling algorithm...
Fast and Simple Approximation Schemes for Generalized Flow (1999)
Lisa 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 flow, and minimum cost multicommodity flow....
A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow (1999)
Lisa Fleischer, Satoru Iwata, S. Thomas Mccormick
We describe an O(n 4 hminflog U; n 2 log ng) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds-- Karp capacity scaling algorithm...
Fast and Simple Approximation Schemes for Generalized Flow (1999)
Lisa 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 flow, and minimum cost multicommodity flow....
A Strongly Polynomial-Time Algorithm For Minimizing Submodular Functions (1999)
Satoru Iwata, Lisa Fleischer, Satoru Fujishige
This paper presents a combinatorial polynomial-time algorithm for minimizing submodular set functions. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the...