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 L2 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) ]