CiteSeerX Scientific Literature Digital Library and Search Engine
CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge
Improved Bounds for Sum Multicoloring and Scheduling Dependent Jobs with Minsum Criteria - Rajiv Gandhi, et al.
We consider a general class of scheduling problems where a set of dependent jobs needs to be scheduled (preemptively or non-preemptively) on a set of machines so as to minimize the weighted sum of completion times. The dependencies among the jobs are formed as an arbitrary conflict graph. An input to our problems can be modeled as an instance of the sum multicoloring (SMC) problem: Given a graph and the number of colors required by each vertex, find a proper multicoloring which minimizes the sum over all vertices of the largest color assigned to each vertex. In the preemptive case...
Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions - Alvin E. Roth
The deferred acceptance algorithm proposed by Gale and Shapley (1962) has had a profound influence on market design, both directly, by being adapted into practical matching mechanisms, and, indirectly, by raising new theoretical questions. Deferred acceptance algorithms are at the basis of a number of labor market clearinghouses around the world, and have recently been implemented in school choice systems in Boston and New York City. In addition, the study of markets that have failed in ways that can be fixed with centralized mechanisms has led to a deeper understanding of some of the tasks a marketplace needs to accomplish...
K-D Trees Are Better when Cut on the Longest Side - Matthew Dickerson; Christian A. Duncan; Michael T. Goodrich
We show that a popular variant of the well known k-d tree data structure satisfies an important packing lemma. This variant is a binary spatial partitioning tree T defined on a set of n points in IR d, for fixed d ≥ 1, using the simple rule of splitting each node’s hyper-rectangular region with a hyperplane that cuts the longest side. An interesting consequence of the packing lemma is that standard algorithms for performing approximate nearest-neighbor searching or range searching queries visit at most O(log d−1 n) nodes of such a tree T in the worst case. Traditionally, many variants...
Sorting in parallel external-memory multicores - Michael T. Goodrich; Michael Nelson; Nodari Sitchinava
In this paper, we introduce a model for multicore architectures, which takes into explicit consideration the cache-oriented nature of inputs and outputs in modern CPUs. In addition, we study the fundamental problem of sorting comparable items using this model. We provide algorithms that are efficient in terms of the number of parallel I/O’s. We also provide lower bounds that show that our algorithms are within a constant factor of optimal, for reasonable values of parameters characterizing the number of processors, the size of each processors memory, the size of cache blocks, and the number of items to be sorted.
Limits on the Efficiency of One-Way Permutation-Based Hash Functions - Jeong Han Kim; Daniel R. Simon; Prasad Tetali
Naor and Yung show that a one-bit-compressing universal one-way hash function (UOWHF) can be constructed based on a one-way permutation. This construction can be iterated to build a UOWHF which compresses by εn bits, at the cost of εn invocations of the one-way permutation. We show that this construction is not far from optimal, in the following sense: there exists an oracle relative to which there exists a oneway permutation with inversion probability 2 −p(n) (for any p(n) ∈ ω(log n)), but any construction of an εn-bit-compressing UOWHF requires Ω ( � n/p(n)) invocations of the one-way permutation, on average....
Balanced Aspect Ratio Trees Revisited - Amitabh Chaudhary; Michael T. Goodrich
Spatial databases support a variety of geometric queries on point data such as range searches, nearest neighbor searches, etc. Balanced Aspect Ratio (BAR) trees are hierarchical space decomposition structures that are general-purpose and space-efficient, and, in addition, enjoy a worst case performance poly-logarithmic in the number of points for approximate queries. They maintain limits on their depth, as well as on the aspect ratio (intuitively, how skinny the regions can be). BAR trees were initially developed for 2 dimensional spaces and a fixed set of partitioning planes, and then extended to d dimensional spaces and more general partitioning planes. Here...
RAMSEY GAMES AGAINST A ONE-ARMED BANDIT - EHUD FRIEDGUT, YOSHIHARU KOHAYAKAWA, VOJTĚCH RÖDL; Andrzej Ruciński; Prasad Tetali
We study the following one-person game against a random graph: the Player’s goal is to 2-colour a random sequence of edges e1, e2,... of a complete graph on n vertices, avoiding a monochromatic triangle for as long as possible. The game is over when a monochromatic triangle is created. The online version of the game requires that the Player should colour each edge when it comes, before looking at the next edge. While it is not hard to prove that the expected length of this game is about n 4/3, the proof of the upper bound suggests the following relaxation:...
Shape-Free Statistical Information in Optical Character Recognition - Scott Leishman
The fundamental task facing Optical Character Recognition (OCR) systems involves the conversion of input document images into corresponding sequences of symbolic character codes. Traditionally, this has been accomplished in a bottom-up fashion: the image of each symbol is isolated, then classified based on its pixel intensities. While such shape-based classifiers are initially trained on a wide array of fonts, they still tend to perform poorly when faced with novel glyph shapes. In this thesis, we attempt to bypass this problem by pursuing a top-down “codebreaking” approach. We assume no a priori knowledge of character shape, instead relying on statistical information...
ON THE COVER TIME OF PLANAR GRAPHS - Johan Jonasson; Oded Schramm
The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any n-vertex, connected graph is at least � 1+o(1) � n log n and at most � 1+o(1) � 4 27 n³. This paper proves that for bounded-degree planar graphs the cover time is at least cn(log n)², and at most 6n², where c is a positive constant depending only on the maximal degree of the graph. The lower bound is established via use...
Delta-Confluent Drawings - David Eppstein; Michael T. Goodrich; Jeremy Yu Meng
We generalize the tree-confluent graphs to a broader class of graphs called ∆-confluent graphs. This class of graphs and distance-hereditary graphs, a well-known class of graphs, coincide. Some results about the visualization of ∆-confluent graphs are also given.
Hardware-assisted natural neighbor interpolation - Quanfu Fan; Alon Efrat; Vladlen Koltun; Shankar Krishnan; Suresh Venkatasubramanian
Natural neighbor interpolation is a weighted average interpolation method that is based on Voronoi tessellation. In this paper, we present and implement an algorithm to perform natural neighbor interpolation using graphics hardware. Unlike traditional software-based approaches that process one query at a time, we develop a scheme that computes the entire scalar field induced by natural neighbor interpolation, at which point a query is a trivial array lookup, and range queries over the field are easy to perform. Our approach is faster than the best known software implementations, and makes use of general purpose stream programming capabilities of current graphics...
Foundational Algorithms for Distributed Robot Swarms - Michael T. Goodrich; David Eppstein; Nodari Sitchinava
In this paper, we study discrete swarm algorithms, where mobile robots (or “mobots”) move around interacting in an environment to solve computational problems. This work extends recent work on swarm algorithms in the distributed computing, artificial intelligence, and robotics literatures in that we allow for mobots to have additional memory so as to enable computations that are somewhat more sophisticated than finite state automata. We describe efficient swarm algorithms for a number of foundational problems, which are essential prerequisites for coordinated movement, data gathering, and data processing computations, including rectangle ranking, prefix sums and products, permutation routing, and sorting. Each...
On the precision of the spectral profile - Gady Kozma
We examine the spectral profile bound of Goel, Montenegro and Tetali for the L ∞ mixing time of continuous-time random walk in reversible settings. We find that it is precise up to a log log factor, and that this log log factor cannot be improved.