F. Frances Yao

MFCS Conference 2005 Conference Paper

An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules

• Minming Li
• F. Frances Yao

Abstract We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O ( dn log n ) time. Previous approaches solve this problem by first computing the optimal continuous solution in O ( n 3 ) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O ( n log n ) time is required, hence the algorithm is optimal for fixed d.

FOCS Conference 1995 Conference Paper

A Scheduling Model for Reduced CPU Energy

• F. Frances Yao
• Alan J. Demers
• Scott Shenker

The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.

FOCS Conference 1994 Conference Paper

Multi-Index Hashing for Information Retrieval

• Daniel H. Greene
• Michal Parnas
• F. Frances Yao

We describe a technique for building hash indices for a large dictionary of strings. This technique permits robust retrieval of strings from the dictionary even when the query pattern has a significant number of errors. This technique is closely related to the classical Turan problem for hypergraphs. We propose a general method of multi-index construction by generalizing certain Turan hypergraphs. We also develop an accompanying theory for analyzing such hashing schemes. The resulting algorithms have been implemented and can be applied to a wide variety of recognition and retrieval problems. >

FOCS Conference 1993 Conference Paper

Approximating Shortest Superstrings

• Shang-Hua Teng
• F. Frances Yao

The Shortest Superstring Problem is to find a shortest possible string that contains every string in a given set as substrings. This problem has applications to data compression and DNA sequencing. As the problem is NP-hard and MAX SNP-hard, approximation algorithms are of interest. We present a new algorithm which always finds a superstring that is at most 2. 89 times as long as the shortest superstring. Our result improves the 3-approximation result of Blum, Jiang, Li, Tromp, and Yannakakis (1991). >

SODA Conference 1990 Conference Paper

Optimal Binary Space Partitions for Orthogonal Objects

• Mike Paterson
• F. Frances Yao

FOCS Conference 1986 Conference Paper

Finite-Resolution Computational Geometry

• Daniel H. Greene
• F. Frances Yao

Geometric algorithms are usually designed with continuous parameters in mind. When the underlying geometric space is intrinsically discrete, as is the case for computer graphics problems, such algorithms are apt to give invalid solutions if properties of a finite-resolution space are not taken into account. In this paper we discuss an approach for transforming geometric concepts and algorithms from the continuous domain to the discrete domain. As an example we consider the discrete version of the problem of finding all intersections of a collection of line segments. We formulate criteria for a satisfactory solution to this problem, and design an interface between the continuous domain and the discrete domain which supports certain invariants. This interface enables us to obtain a satisfactory solution by using plane-sweep and a variant of the continued fraction algorithm.

STOC Conference 1985 Conference Paper

A General Approach to d-Dimensional Geometric Queries (Extended Abstract)

• Andrew Chi-Chih Yao
• F. Frances Yao

STOC Conference 1983 Conference Paper

A 3-Space Partition and Its Applications (Extended Abstract)

• F. Frances Yao

STOC Conference 1980 Conference Paper

Efficient Dynamic Programming Using Quadrangle Inequalities

• F. Frances Yao

Dynamic programming is one of several widely used problem-solving techniques in computer science and operation research. In applying this technique, one always seeks to find speed-up by taking advantage of special properties of the problem at hand. However, in the current state of art, ad hoc approaches for speeding up seem to be characteristic; few general criteria are known. In this paper we give a quadrangle inequality condition for rendering speed-up. This condition is easily checked, and can be applied to several apparently different problems. For example, it follows immediately from our general condition that the construction of optimal binary search trees may be speeded up from O(n 3 ) steps to O(n 2 ), a result that was first obtained by Knuth using a different and rather complicated argument.

FOCS Conference 1980 Conference Paper

On the Priority Approach to Hidden-Surface Algorithms (Preliminary Report)

• F. Frances Yao

The task of eliminating invisible parts when generating an image is one of the central problems in computer graphics. One approach achieves the desired obscuring effect by assigning priority numbers to the faces of an object. Image generation can be speeded up significantly in these priority schemes if priority information of the faces can be partly computed in advance, before a viewing position is specified. These observations were first made by Schumacker and are utilized to advantage in simulation applications. However, the priority calculations are usually done manually, for lack of an adequate theoretical understanding. In this paper we study the underlying mathematical structure of these priority orders, and present efficient algorithms for handling some special classes of geometrical configurations.

STOC Conference 1980 Conference Paper

On Translating a Set of Rectangles

• Leonidas J. Guibas
• F. Frances Yao

Given a collection of disjoint objects in the plane, we are interested in translating them by a common vector. If we have a primitive for translating one object at a time, then the order in which the objects can individually be translated is often geometrically constrained. In this paper we study the nature of these constraints and exhibit optimal algorithms for finding valid motion ordering for several different classes of objects. These algorithms find use in computer display applications.

FOCS Conference 1978 Conference Paper

On the Average-case Complexity of Selecting k-th Best

• Andrew Chi-Chih Yao
• F. Frances Yao

Let Vk (n) be the minimum average number of pairwise comparisons needed to find the k-th largest of n numbers (k≥2), assuming that all n! orderings are equally likely. D. W. Matula proved that, for some absolute constant c, Vk(n)- n ≤ ck log log n as n → ∞. In the present paper, we show that there exists an absolute constant c′ ≫ 0 such that Vk(n) - n ≥ c′k log log n as n → ∞, proving a conjecture by Matula.

FOCS Conference 1976 Conference Paper

The Complexity of Searching an Ordered Random Table (Extended Abstract)

• Andrew Chi-Chih Yao
• F. Frances Yao