Inferring Tree Models for Oncogenesis from Comparative Genome Hybridization Data
Comparative genome hybridization (CGH) is a laboratory method to measure gains and losses of chromosomal regions in tumor cells. It is believed that DNA gains and losses in tumor cells do not occur entirely at random, but partly through some flow of causality. Models that relate tumor progression to the occurrence of DNA gains and losses could be very useful in hunting cancer genes and in cancer diagnosis. We lay some mathematical foundations for inferring a model of tumor progression from a CGH data set. We consider a class of tree models that are more general than a path model that has been developed for colorectal cancer. We derive a tree model inference algorithm based on the idea of a maximum-weight branching in a graph, and we show that under plausible assumptions our algorithm infers the correct tree. We have implemented our methods in software, and we illustrate with a CGH data set for renal cancer.

title: On the Difficulty of Designing Good Classifiers
abstract: It is a very interesting and well-studied problem, given two point sets W, B\(\subseteq\)ℜn, to design a linear decision tree that classifies them —that is, no leaf subdivision contains points from both B and W — and is as simple as possible, either in terms of the total number of nodes, or in terms of its depth. We show that, unless ZPP=NP, the depth of a classifier cannot be approximated within a factor smaller than 6/5, and that the total number of nodes cannot be approximated within a factor smaller than n1/5. Our proof relies on a simple connection between this problem and graph coloring, and uses recent nonapproximability results for graph coloring. We also study the problem of designing a classifier with a single inequality that involves as few variables as possible, and point out certain aspects of the difficulty of this problem.

title: On the Complexity of Database Queries
abstract: We revisit the issue of the complexity of database queries, in the light of the recent parametric refinement of complexity theory. We show that, if the query size (or the number of variables in the query) is considered as a parameter, then the relational calculus and its fragments (conjunctive queries, positive queries) are classified at appropriate levels of the so-called W hierarchy of Downey and Fellows. These results strongly suggest that the query size is inherently in the exponent of the data complexity of any query evaluation algorithm, with the implication becoming stronger as the expressibility of the query language increases. On the positive side, we show that this exponential dependence can be avoided for the extension of acyclic queries with ? (but not <) inequalities.

title: The serializability of concurrent database updates
abstract: A sequence of interleaved user transactions in a database system may not be ser:ahzable, t e, equivalent to some sequential execution of the individual transactions Using a simple transaction model, it ~s shown that recognizing the transaction histories that are serlahzable is an NP-complete problem. Several efficiently recognizable subclasses of the class of senahzable histories are therefore introduced; most of these subclasses correspond to senahzabdity principles existing in the hterature and used in practice Two new principles that subsume all previously known ones are also proposed Necessary and sufficient conditions are given for a class of histories to be the output of an efficient history scheduler, these conditions imply that there can be no efficient scheduler that outputs all of senahzable histories, and also that all subclasses of senalizable histories studied above have an efficient scheduler Finally, it is shown how these results can be extended to far more general transaction models, to transactions with partly interpreted functions, and to distributed database systems

title: The 1-Steiner Tree Problem
abstract: We present an O ( n 2 ) algorithm for finding the point on the plane which, if added to a given set of n points, will result in the shortest possible spanning tree.

title: Optimization, approximation, and complexity classes
abstract: We define a natural variant of NP, MAX NP, and also a subclass called MAX SNP. These are classes of optimization problems, and in fact contain several natural, well-studied ones. We show that problems in these classes can be approximated with some bounded error. Furthermore, we show that a number of common optimization problems are complete under a kind of careful transformation (called L-reduction) that preserves approximability. It follows that such a complete problem has a polynomial-time approximation scheme iff the whole class does. These results may help explain the lack of progress on the approximability of a host of optimization problems.

title: The complexity of recognizing polyhedral scenes
abstract: Given a drawing of straight lines on the plane, we wish to decide whether it is the projection of the visible part of a set of opaque polyhedra. Although there is an extensive literature and reports on empirically succesful algorithm: for this problem, there has been no definite result concerning its complexity. In this paper we show that, rather surprisingly, this problem is NP-complete. This is true even in the relatively simple case of trihedral scenes (no four planes share a point) without shadows or cracks. Despite this negative result, we present a fast algorithm for the important special case of orthohedral scenes (all planes are perpendicular to one of the three axes) with a fixed number of "possible" objects.

title: An approximation scheme for planar graph TSP
abstract: We consider the special case of the traveling salesman problem (TSP) in which the distance metric is the shortest-path metric of a planar unweighted graph. We present a polynomial-time approximation scheme (PTAS) for this problem.

title: Topological Queries

title: Topological Queries in Spatial Databases
abstract: We studytopological queriesover two-dimensional spatial databases. First, we show that the topological properties of semi-algebraic spatial regions can be completely specified using a classical finite structure, essentially the embedded planar graph of the region boundaries. This provides aninvariantcharacterizing semi-algebraic regions up to homeomorphism. All topological queries on semi-algebraic regions can be answered by queries on the invariant whose complexity is polynomially related to the original. Also, we show that for the purpose of answering topological queries, semi-algebraic regions can always be represented simply as polygonal regions. We then study query languages for topological properties of two-dimensional spatial databases, starting from the topological relationships between pairs of planar regions introduced by Egenhofer. We show that the closure of these relationships under appropriate logical operators yields languages which arecompletefor topological properties. This provides a theoreticala posteriorijustification for the choice of these particular relationships. Unlike the point-based languages studied in previous work on constraint databases, our languages are region based?quantifiers range over regions in the plane. This yields a family of languages, whose complexity ranges fromNCto undecidable. Another type of completeness result shows that the region-based language of complexityNCexpresses precisely the same topological properties as well-known point-based languages.

title: On the approximability of trade-offs and optimal access of Web sources
abstract: We study problems in multiobjective optimization, in which solutions to a combinatorial optimization problem are evaluated with respect to several cost criteria, and we are interested in the trade-off between these objectives (the so-called Pareto curve). We point out that, under very general conditions, there is a polynomially succinct curve that /spl epsiv/-approximates the Pareto curve, for any /spl epsiv/>0. We give a necessary and sufficient condition under which this approximate Pareto curve can be constructed in time polynomial in the size of the instance and 1//spl epsiv/. In the case of multiple linear objectives, we distinguish between two cases: when the underlying feasible region is convex, then we show that approximating the multi-objective problem is equivalent to approximating the single-objective problem. If however the feasible region is discrete, then we point out that the question reduces to an old and recurrent one: how does the complexity of a combinatorial optimization problem change when its feasible region is intersected with a hyperplane with small coefficients; we report some interesting new findings in this domain. Finally, we apply these concepts and techniques to formulate and solve approximately a cost-time-quality trade-off for optimizing access to the World-Wide Web, in a model first studied by Etzioni et al. (1996) (which was actually the original motivation for this work).