Sharing the Cost of Multicast Transmissions
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in this context. We prove that the former has a natural algorithm that uses only two messages per link of the multicast tree, while we give evidence that the latter requires a quadratic total number of messages. We also show that the welfare value achieved by an optimal multicast tree is NP-hard to approximate within any constant factor, even for bounded-degree networks. The lower-bound proof for the Shapley value uses a novel algebraic technique for bounding from below the number of messages exchanged in a distributed computation; this technique may prove useful in other contexts as well.

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: 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: 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 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: 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).

title: Optimum Grip of a Polygon
abstract: It has been shown by Baker, Fortune and Grosse that any two-dimensional polygonal object can be prehended stably with three fingers, so that its weight (along the third dimension) is balanced. Besides, in this paper we show that form closure of a polygon object can be achieved by four fingers (previous proofs were not complete). We formulate and solve the problem of finding the optimum stable grip or form closure of any given polygon. For stable grip it is most natural to minimize the forces needed to balance through friction the object''s weight along the third dimension. For form closure, we minimize the worst-case forces needed to balance any unit force acting on the center of gravity of the object. The mathematical techniques used in the two instances are an interesting mix of Optimization and Euclidean geometry. Our results lead to algorithms for the efficient computation of the optimum grip in each case.

title: Reducibility among equilibrium problems
abstract: We address the fundamental question of whether the Nash equilibria of a game can be computed in polynomial time. We describe certain efficient reductions between this problem for normal form games with a fixed number of players and graphical games with fixed degree. Our main result is that the problem of solving a game for any constant number of players, is reducible to solving a 4-player game.

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: 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.