Philip N. Klein
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Philip N. Klein has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
Hsueh-I Lu
2 shared publications- Ramamoorthi Ravi
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
2 shared publications - Ajit Agrawal
Exa Corporation, Cambridge
1 shared publication - Balaji Raghavachari
Department of Computer Science The University of Texas at Dallas Box 830688 75083-0688 Richardson TX
1 shared publication - Cliff Stein
Dartmouth College
1 shared publication - David R. Karger
MIT Laboratory for Computer Science 02138 Cambridge MA
1 shared publication
Latest Publications
- Open Access
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter*n*log(n)) Time
We develop a new technique for computing maximum flow in directed planar graphs with multiple sources and a single sink that significantly deviates from previously known techniques for flow problems. This gives rise to an O(diameter*n*log(n)) algorithm for the problem.
Open AccessMultiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter*n*log(n)) Time
We develop a new technique for computing maximum flow in directed planar graphs with multiple sources and a single sink that significantly deviates from previously known techniques for flow problems. This gives rise to an O(diameter*n*log(n)) algorithm for the problem.
- Open Access
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even NP-hard to approximate within 1+delta for some small delta > 0. Calinescu, Karloff, and Rabani (1998) gave an algorithm with performance guarantee 3/2-1/k, based on a geometric relaxation of the problem. In this paper, we give improved randomized rounding schemes for their relaxation, yielding a 12/11-approximation algorithm for k=3 and a 1.3438-approximation algorithm in general. Our approach hinges on the observation that the problem of designing a randomized rounding scheme for a geometric relaxation is itself a linear programming problem. The paper explores computational solutions to this problem, and gives a proof that for a general class of geometric relaxations, there are always randomized rounding schemes that match the integrality gap.
Open AccessRounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even NP-hard to approximate within 1+delta for some small delta > 0. Calinescu, Karloff, and Rabani (1998) gave an algorithm with performance guarantee 3/2-1/k, based on a geometric relaxation of the problem. In this paper, we give improved randomized rounding schemes for their relaxation, yielding a 12/11-approximation algorithm for k=3 and a 1.3438-approximation algorithm in general. Our approach hinges on the observation that the problem of designing a randomized rounding scheme for a geometric relaxation is itself a linear programming problem. The paper explores computational solutions to this problem, and gives a proof that for a general class of geometric relaxations, there are always randomized rounding schemes that match the integrality gap.
- 1 April 2003
- Published by Springer Nature in Algorithmica
- Vol. 35 (4) , 321-345
Detecting Race Conditions in Parallel Programs that Use Semaphores
- 1 April 2003
- Published by Springer Nature in Algorithmica
- Vol. 35 (4) , 321-345
Detecting Race Conditions in Parallel Programs that Use Semaphores
- Open Access
Detecting Race Conditions in Parallel Programs that Use Semaphores
We address the problem of detecting race conditions in programs that use semaphores for synchronization. Netzer and Miller showed that it is NP-complete to detect race conditions in programs that use many semaphores. We show in this paper that it remains NP-complete even if only two semaphores are used in the parallel programs. For the tractable case, i.e., using only one semaphore, we give two algorithms for detecting race conditions from the trace of executing a parallel program on p processors, where n semaphore operations are executed. The first algorithm determines in O(n) time whether a race condition exists between any two given operations. The second algorithm runs in O(np log n) time and outputs a compact representation from which one can determine in O(1) time whether a race condition exists between any two given operations. The second algorithm is near-optimal in that the running time is only O(log n) times the time required simply to write down the output.
Open AccessDetecting Race Conditions in Parallel Programs that Use Semaphores
We address the problem of detecting race conditions in programs that use semaphores for synchronization. Netzer and Miller showed that it is NP-complete to detect race conditions in programs that use many semaphores. We show in this paper that it remains NP-complete even if only two semaphores are used in the parallel programs. For the tractable case, i.e., using only one semaphore, we give two algorithms for detecting race conditions from the trace of executing a parallel program on p processors, where n semaphore operations are executed. The first algorithm determines in O(n) time whether a race condition exists between any two given operations. The second algorithm runs in O(np log n) time and outputs a compact representation from which one can determine in O(1) time whether a race condition exists between any two given operations. The second algorithm is near-optimal in that the running time is only O(log n) times the time required simply to write down the output.
- 1 June 1995
- Published by Springer Nature in Combinatorica
- Vol. 15 (2) , 187-202
An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
- 1 June 1995
- Published by Springer Nature in Combinatorica
- Vol. 15 (2) , 187-202
An approximate max-flow min-cut relation for undirected multicommodity flow, with applications