How does one model the browsing activity on the WWW, which incorporates the use of both hyperlinks and `back buttons'? A recent paper proposes and analyzes a new random walk model with the notion of such backoff processes.

A recent paper (SODA '99)
gives a (*3/2 + e*)-factor approximation algorithm (for any *e
> 0*) for the metric Steiner tree problem for the special case of
quasi-bipartite graphs. These are graphs that do not have edges
connecting pairs of Steiner vertices.

In the k*-medians problem*, given a set *S* of *n*
points in a metric space and a positive integer *k*, the goal is
to locate *k* medians in the space such that the sum of the
distances from each of the points of *S* to the nearest median is
minimized. A paper (STOC
'98) obtains the first polynomial time approximation schemes for the
Euclidean *k*-medians problem.

*Recommendation systems* track past actions of a group of users
to make recommendations to individual members of the group. The
growth of computer-mediated marketing and commerce has led to
increased interest in such systems. A paper (FOCS '98) introduces a simple
analytical framework for recommendation systems, including a basis for
defining the utility of such a system and some algorithmic methods.

* Segmentation problems * are a novel genre of optimization
problems that are motivated by certain aspects of clustering and data
mining. A paper (STOC '98)
introduces this model and devises approximation algorithms for a
number of such problems.

Reliability of various storage and transmission channels, such as magnetic/optical disk drives, can be substantially improved by matching the characteristics of the recorded or transmitted signals to those of the channel. Constrained codes are used to convert an arbitrary source signal to a coded signal that satisfies a given channel constraint. Group members have classified the computational complexities of several fundamental problems in the field of constrained block coding. For example, certain problems of minimizing the size of logic circuits for block encoders and decoders are shown to be complete in the second and third levels of the polynomial-time hierarchy. The apparent intractability of these problems does not diminish the practical need to solve them. A recent paper (IEEE JSAC '00) (joint work with Storage Systems and Technology proposes heuristic algorithms for the problems of minimizing the size of logic circuits for block encoders and decoders.

*Delta compression * is the algorithmic task of finding common
strings between versions of data and using the commonality between
versions to compactly encode one version by describing it as a set of
changes from its companion. Delta compression can be applied, for
example, to reduce the network bandwidth required for backup/restore
and for software updating. In work with the Storage Systems
department, group members have invented new techniques and algorithms
with good compression performance for this problem. A
paper
is available. These algorithms are the basis for the Adaptive Differencing
Technology that is now being incorporated in the
Tivoli Storage Manager product.
(See also.)

Online scheduling and resource allocation problems also arise in the context of parallel database and network servers. A paper (SODA '98) contains algorithms with a new notion of fairness that minimizes the maximum slowdown factor of a job because of other jobs competing for resources. Another paper (JPDC '98) provides algorithms for sharing resources at a given time, such as allocating a fraction of processors to each competing job.

In the area of storage systems, problems often arise because of the unpredictable nature of I/O requests. A paper (HPCS '98) introduces and evaluates a new algorithm for garbage collection in log-structured disk arrays and file systems.

Checking computations/properties via careful random sampling is a quick and useful paradigm for ensuring the correctness of programs. The problem of checking the associativity of tables is considered in a paper (FOCS '96), where a randomized quadratic-time algorithm is given.

The problem of whether a prover can aid a verifier to reliably compute
a function faster than if the verifier were to compute the function on
its own is considered in a recent
paper (STOC '99). It is sufficient for the verifier to know that
the answer is close to correct. The model used is based on
interactive proof systems, probabilistically checkable proofs, program
checkers, and CS proofs. The model of * spot-checking * is
introduced in a paper
(STOC '98) where checkers in this model for some basic problems are
given.

Lattices play an important role in many algebraic and combinatorial
algorithms. A long standing open problem has been to understand the
complexity of computing the shortest non-zero vector in a lattice. A
paper (STOC '98) resolves this question by showing that the
shortest vector problem in L_{2} is
**NP**-hard for randomized reductions. Another paper (STRUCTURES '99) shows that the
uniqueness version of this problem is also **NP**-hard. Techniques
for generating hard instances of the short basis problem will be
presented as an invited talk
(ICALP '99).

* Descriptive complexity * is the complexity of describing
problems in some logical formalism. There is often a close connection
between the descriptive complexity of a problem and its computational
complexity. A paper (STOC
'98) on the topic discusses the closure of monadic ** NP **.

* *

**
[
IBM Research |
IBM home page |
Order |
Search |
Contact IBM |
Help |
(C) |
(TM)
]
**