Lawrence L. Larmore
Encyclopedia
Competitive analysis (online algorithm)
Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance...
of online algorithm
Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
s, particularly for the k-server problem
K-server problem
The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis...
. His contributions, with his co-author Marek Chrobak
Marek Chrobak
Marek Chrobak is a full professor at University of California, Riverside. He is known for his work competitive analysis of online algorithms, particularly for the k-server problem. His contributions, with his co-author Lawrence L...
, led to the application of T-theory
T-theory
T-theory is a branch of discrete mathematics dealing with analysis of trees and discrete metric spaces.-General history:As per Andreas Dress, T-theory originated from a question raised by Manfred Eigen, a recipient of the Nobel Prize in Chemistry, in the late seventies. He was trying to fit twenty...
to the server problem. In addition, he developed the package-merge algorithm
Package-merge algorithm
The package-merge algorithm is an O-time algorithm for finding an optimal length-limited Huffman code for a given distribution on a given alphabet of size n, where no code word is longer than L. It is a greedy algorithm, and a generalization of Huffman's original algorithm...
for the length-limited Huffman coding
Huffman coding
In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol where the variable-length code table has been derived in a particular way based on...
problem, as well as an algorithm for optimizing paragraph breaking in linear time.
He earned a Ph.D. in Mathematics in the field of algebraic topology
Algebraic topology
Algebraic topology is a branch of mathematics which uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism, though usually most classify up to homotopy equivalence.Although algebraic topology...
from Northwestern University
Northwestern University
Northwestern University is a private research university in Evanston and Chicago, Illinois, USA. Northwestern has eleven undergraduate, graduate, and professional schools offering 124 undergraduate degrees and 145 graduate and professional degrees....
in 1965. He later earned a second Ph.D., this time in Computer Science, in the field of theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
from University of California, Irvine. He is a Past Member of Institute for Advanced Study in Princeton, NJ
Institute for Advanced Study
The Institute for Advanced Study, located in Princeton, New Jersey, United States, is an independent postgraduate center for theoretical research and intellectual inquiry. It was founded in 1930 by Abraham Flexner...
and Gastwissenschaftler at the University of Bonn
University of Bonn
The University of Bonn is a public research university located in Bonn, Germany. Founded in its present form in 1818, as the linear successor of earlier academic institutions, the University of Bonn is today one of the leading universities in Germany. The University of Bonn offers a large number...
.