| Large Scale Visual Recognition |
Jun 2012 |
162 pages |
| Authors:
Jia Deng; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
 | Visual recognition remains one of the grand goals of artificial intelligence research. One major challenge is endowing machines with human ability to recognize tens of thousands of categories. Moving beyond previous work that is mostly focused on hundreds of categories we make progress toward human scale visual recognition. Specifically, our contributions are as follows First, we have constructed ImageNet, a large scale image ontology. The Fall 2011 version consists of ... |
|
| Dynamic and Supervised Topic Models for Literature-Based Discovery |
21 Dec 2011 |
7 pages |
| Authors:
David M Blei; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| Under the support of the ONR my research focused on extending the state ot the an or probabilistic topic modeling, algorithms for making discoveries from and predictions about large collections of texts. For the past three years, my group has published many papers in the service of this goal. In this report, I will highlight some of the themes and publications that represent this work. Thanks to the support of ... |
|
| Scalable Management of Enterprise and Data-Center Networks |
Sep 2011 |
151 pages |
| Authors:
Minlan Yu; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| The networks in campuses, companies, and data centers are growing larger and becoming more complicated to manage. Today, network operators devote tremendous time and effort to three key management tasks--routing, access control, and troubleshooting. Rather than trying to make today's brittle networks easier to manage, we focus on new network designs that are inherently easier to manage and scale to many hosts, switches, and applications. We design and develop a ... |
|
| Scaling Proof-Carrying Code to Production Compilers and Security Policies |
APR 2005 |
18 pages |
| Authors:
Andrew W. Appel; Edward W. Felton; David P. Walker; Zhong Shao; Valery Trifonov; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| We have developed high-assurance software protection mechanisms that can be used in component-software platforms (virtual machines such as Sun's Java or Microsoft's .Net). The idea is to leverage type-safe source languages to get fine-grained protection at the level of individual object fields and methods. The obstacle to be overcome was the inherent complexity of virtual machine implementations, particularly their just-in-time compiler, before installing that output for execution. We have successfully ... |
|
| AASERT: Software Tools for Experimentation in Computational Geometry |
05 FEB 2001 |
5 pages |
| Authors:
David Dobkin; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| This research has considered problems in computer graphics and visualization. The work has aimed to bring theoretical tools to practical problems as well as to develop tools with which to aid in the building of geometric software. The problem of creating a parameterization of the surface of a mesh that can be applied at multiple resolutions has been studied. Such a parameterization has a number of applications. We were originally ... |
|
| DNA Computation: The Search for the "Killer" Application |
MAR 2000 |
2 pages |
| Authors:
R. J. Lipton; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| We successfully expanded the field of DNA Computers to RNA to develop and execute a general approach for the solution of Satisfiability problems. A challenge to this field has been the need for a design that is scalable to more difficult computations. |
|
| More Efficient Bottom-Up Tree Pattern Matching |
MAY 90 |
16 pages |
| Authors:
J. Cai; R. Paige; R. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| Pattern matching in trees is fundamental to a variety of programming language systems. However, progress has been slow in satisfying a pressing need for general purpose pattern matching algorithms that are efficient in both time and space. We offer asymptotic improvements in both time and space to Chase's bottom-up algorithm for pattern preprocessing. Our preprocessing algorithm has the additional advantage of being incremental with respect to pattern additions and deletions. ... |
|
| Short Encodings of Evolving Structures |
APR 90 |
27 pages |
| Authors:
Daniel D. Sleator; Robert E. Tarjan; William P. Thurston; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| A derivation in a transformational system such as a graph grammar may be redundant in the sense that the exact order of the transformations may not affect the final outcome; all that matters is that each transformation, when applied, is applied to the correct structure. By taking advantage of this redundancy, we are able to develop an efficient encoding scheme for such derivations. This encoding scheme has a number of ... |
|
| Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph |
JAN 90 |
31 pages |
| Authors:
David Eppstein; Giuseppe F. Italiano; Roberto Tamassia; Robert E. Tarjan; Jeffery Westbrook; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| We give efficient algorithms for maintaining a minimum spanning forest of a planar graph subject to on-line modifications. The modifications supported include changes in the edge weights, and insertion and deletion of edges and vertices. To implement the algorithms, we develop a data structure called an edge-ordered dynamic tree, which is a variant of the dynamic tree data structure of Sleator and Tarjan. Using this data structure, our algorithms run ... |
|
| Unique Binary Search Tree Representations and Equality-Testing of Sets and Sequences |
NOV 89 |
15 pages |
| Authors:
Rajamani Sundar; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| Given an ordered universe U, we study the problem of representing each subset of U by a unique binary search tree so that dictionary operations can be performed efficiently. We exhibit representations that permit the execution of dictionary operations in optimal time when the dictionary is sufficiently sparse or sufficiently dense. We apply unique representations to obtain efficient data structures for maintaining a collection of sets/sequences under queries that test ... |
|
| Maintaining Bridge-Connected and Biconnected Components On-Line |
AUG 89 |
41 pages |
| Authors:
Jeffrey Westbrook; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| We consider the twin problems of maintaining the bridge-connected components and the biconnected components of a dynamic undirected graph. The allowed changes to the graph are vertex and edge insertions. We give an algorithm for each problem. With simple data structures, each algorithm runs in O(nlogn+m) time, where n is the number of vertices and m is the number of operations. We develop a modified version of the dynamic trees ... |
|
| Simplified Linear-Time Jordan Sorting and Polygon Clipping |
JUL 89 |
17 pages |
| Authors:
Khun Y. Fung; Tina M. Nicholl; Robert E. Tarjan; Christopher J. Van Wyk; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| The Jordan sorting problem is, given the intersection points of a Jordan curve with the x-axis in the order in which they occur along the x-axis. This problem arises in clipping a simple polygon against a rectangle (a window) and in efficient algorithms for triangulating a simple polygon. Hoffman, Mehlhorn, Rosentiehl, and Tarjan proposed an algorithm that solves the Jordan sorting problem in time linear in the number of intersection ... |
|
| Faster Scaling Algorithms for General Graph Matching Problems |
11 APR 89 |
50 pages |
| Authors:
Harold N. Gabow; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| This paper presents an algorithm for minimum cost matching on a general graph with integral edge costs, that runs in time close to the best known bound for cardinality matching. Specifically, let n, m and N denote the number of vertices, number of edges, and largest magnitude of a cost, respectively. Other applications of the new algorithm are given, including an efficient implementation of Christofides' traveling salesman approximation algorithm and ... |
|
| Network Flow Algorithms |
APR 89 |
80 pages |
| Authors:
Andrew V. Goldberg; Eva Tardos; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| Network flow problems are central problems in operations research, computer science, and engineering and they arise in many real world applications. Starting with early work in linear programming and spurred by the classic book of Ford and Fulkerson, the study of such problems has led to continuing improvements in the efficiency of network flow algorithms. In spite of the long history of this study, many substantial results have been obtained ... |
|
| Almost-Optimum Parallel Speed-Ups of Algorithms for Bipartite Matching and Related Problems |
18 JAN 89 |
33 pages |
| Authors:
Harold N. Gabow; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| This paper focuses on algorithms for matching problems that run on an EREW PRAM with p processors. Given is a bipartite graph with n vertices, m edges, and integral edge costs at most N in magnitude. This bound is within a factor of log p of optimum speed-up of the best known sequential algorithm, which in turn is within a factor of log (nN) of the best known bound for ... |
|
| Efficiency of the Network Simplex Algorithm for the Maximum Flow Problem |
OCT 88 |
19 pages |
| Authors:
Andrew V. Goldberg; Michael D. Grigoriadis; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| Goldfarb and Hao have proposed a network simplex algorithm that will solve a maximum flow problem on an n-vertex, m-arc network in at most nm pivots and O(n squared m) time. In this paper we describe how to implement their algorithm to run in O(nmlog n) time by using an extension of the dynamic tree data structure of Sleator and Tarjan. This bound is less than a logarithmic factor larger ... |
|
| A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network |
OCT 88 |
11 pages |
| Authors:
Andrew V. Goldberg; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| We suppose a simple parallel algorithm for finding a blocking flow in an acyclic network. On an n-vertex, m-arc network, our algorithm runs in O(n log n) time and O(nm) space using an m-processor EREW PRAM. A consequence of our algorithm is an O(n2(log n)log(nC))-time, O(nm)-space, m-processor algorithm for the minimum-cost circulation problem, on a network with integer arc capacities of magnitude at most C. (KR) |
|
| Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem |
AUG 88 |
|
| Authors:
Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
 | We study the number of pivots required by the primal network simplex algorithm to solve the minimum-cost circulation problem. We propose a pivot selection rule with a certain bound on the number of pivots, for an n-vertex network. This is the first known subexponential bound. The network simplex algorithm with this rule can be implemented. In the special case of planar graphs, we obtain a polynomial bound on the number ... |
|
| Transitive Reduction in Parallel via Branchings |
15 JUL 88 |
17 pages |
| Authors:
Phillip Gibbons; Richard Karp; Vijaya Remachandran; Danny Soroker; Robert Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in polylog parallel time and uses O(n cubed) processors on a PRAM. Our algorithm is simple and the major tool it uses is computing a minimum-weight branching with zero-one weights. We also present sequential algorithms for the problem that ... |
|
| Finding Minimum-Cost Flows by Double Scaling |
JUN 88 |
31 pages |
| Authors:
Ravindra K. Ahuja; Andrew V. Goldberg; James B. Orlin; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm log log U(nC)) time on networks with n vertices, m arcs, maximum arc capacity U, and maximum arc cost magnitude C. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja ... |
|
| A Tight Amortized Bound for Path Reversal |
JUN 88 |
7 pages |
| Authors:
David Ginat; Daniel D. Sleator; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| Path reversal is a form of path compression used in a disjoint set union algorithm and a mutual exclusion algorithm. We derive a tight upper bound on the amortized cost of path reversal. (JHD) |
|
| Faster Algorithms for the Shortest Path Problem |
MAR 88 |
|
| Authors:
Ravindra K. Ahuja; Kurt Mehlhorn; James B. Orlin; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| This document investigates efficient implementations of Dijkstra's shortest path algorithm. The authors propose a new data structure, called the redistributive heap, for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C, a one-level form of redistributive heap give a time bound of Dijkstra's algorithm of O(m + n log C). A two-level form of redistributive heap give a bound ... |
|
| Amortized Analysis of Algorithms for Set Union with Backtracking. Revision |
MAR 88 |
|
| Authors:
Jeffrey Westbrook; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| Mannila and Ukkonen have studied a variant of the classical disjoint set union (equivalence) problem in which an extra operation, called deunion, can undo the most recently performed union operation not yet undone. They proposed a way to modify standard set union algorithms to handle deunion operations. This document analyzes several algorithms based on their approach. The most efficient such algorithms have an amortized running time of O(log n/log log ... |
|
| Improved Time Bounds for the Maximum Flow Problem |
SEP 87 |
|
| Authors:
Ravindra K. Ahuma; James B. Orlin; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| A new approach is proposed to the maximum network flow problem. The approach yields a very simple algorithm running O(n-cubed) time on n-vertex networks. Incorporation of the dynamic tree data structure of Sleator and Tarjan yields a more complicated algorithm with a running time of O(nm log (n-squared/ m)) on m-edge networks. A variant of the algorithm is developed that uses scaling and runs in O(nm + (n-sq) log U) ... |
|
| Faster Scaling Algorithms for Network Problems |
AUG 87 |
|
| Authors:
Harold N. Gabow; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| This paper presents algorithms for the assignment problem, the transportation problem and the minimum cost flow problem of operations research. The algorithms finds a minimum cost solution, but run in time close to the best -known bounds for the corresponding problems without costs. For example, the assignment problem (equivalently, minimum cost matching on a bipartite graph) can be solved in O((sq rt n)nm log (nN)) time, where n, m and ... |
|
| A Fast Parametric Maximum Flow Algorithm. Revision |
JUL 87 |
|
| Authors:
Giorgio Gallo; Michael D. Grigoriadis; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| The classical maximum flow problem sometimes occurs in settings in which the capacities are not fixed but are functions of a single parameters, and the goal is to find the value of the parameter such that the corresponding maximum flow or minimum cut satisfies some side condition. Finding the desired parameter value requires solving a sequence of related maximum flow problems. We shoe that the recent maximum flow algorithm of ... |
|
| Finding Minimum-Cost Circulations by Canceling Negative Cycles |
JUL 87 |
|
| Authors:
Andrew V. Goldberg; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of ... |
|
| Finding Minimum-Cost Circulations by Successive Approximation |
JUL 87 |
|
| Authors:
Andrew V. Goldberg; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| This document develops a new approach to solving minimum-cost circulation problems. This approach combines methods for solving the maximum flow problem with successive approximation techniques based on cost scaling. The authors measure the accuracy of a solution by the amount that the complementary slackness conditions are violated. They propose a simple minimum-cost circulation algorithm, one version of which runs in O(cu n log(nC)) time on an n-vertex network with integer ... |
|
| A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest |
JUL 87 |
|
| Authors:
Harold N. Gabow; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| A pseudoforest is a graph each of whose connected components is a tree or a tree plus an edge; a spanning pseudoforest of a graph contains the greatest number of edges possible. This paper shows that a minimum cost spanning pseudoforest of a graph with n vertices and m edges can be found in O(m + n) time. This implies that a minimum spanning tree can be found in O(m) ... |
|
| Relaxed Heaps: An Alternative to Fibonacci Heaps |
JUL 87 |
|
| Authors:
James R. Driscoll; Harold N. Gabow; Ruth Shrairman; Robert E. Tarjan; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap - a sequence of m decrease key and n delete min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case- o(1) time for decrease key and O(log n) for delete min. A relaxed heap is a type of binomial ... |
|
| Graduate Fellowships for Study in Engineering Sciences and Technology |
07 NOV 86 |
|
| Authors:
Kenneth Steiglitz; Andrea LaPaugh; Susan Yeh; PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
|
| The Weinberger Array Generator (WAG) is a tool for implementing random logic. Boolean equations are input, and a layout description of gates and wires (the circuit) realizing the equations is output. In the above aspects, WAG is similar to a PLA generator. The main difference is that the Weinberger array structure allows many levels of logic, with complex gates such as NAND-of-ORs; whereas a PLA structure allows only two levels ... |
|
Reports by Corporate Author
