Catálogo de publicaciones - libros

Volume computation is a traditional, extremely hard but highly demanding task. It has been widely studied and many interesting theoretical results are obtained in recent years. But very little attention is paid to put theory into use in practice. On the other hand, applications emerging in computer science and other fields require practically effective methods to compute/estimate volume. This paper presents a practical Monte Carlo sampling algorithm on volume computation/estimation and a corresponding prototype tool is implemented. Preliminary experimental results on lower dimensional instances show a good approximation of volume computation for both convex and non-convex cases. While there is no theoretical performance guarantee, the method itself even works for the case when there is only a membership oracle, which tells whether a point is inside the geometric body or not, and no description of the actual geometric body is given.

Interference is a fundamental limiting factor in wireless networks. Due to interaction among transmissions of neighboring nodes and need for multi-hop routing in large networks, it is a non-trivial problem to estimate how much throughput a network can deliver. In an important piece of work, Gupta and Kumar [3] showed that in a random model, where identical nodes are distributed uniformly in a unit square and each node is communicating with a random destination, the capacity of the network as measured in bit-meters/sec is . This result articulates the packing constraint of the paths: on average each path is hops long, and thus in the space of size (), only paths can be accommodated.

We show that minimal -vertex connected spanning subgraphs of a given graph can be generated in incremental polynomial time for any fixed .

Many algorithms seek to compute actual optimal paths in weighted directed graphs. The standard approach for reporting an actual optimal path is based on building a single-source optimal path tree. A technique was given in [1] for a class of problems such that a single actual optimal path can be reported without maintaining any single-source optimal path tree, thus significantly reducing the space bound of those problems with no or little increase in their running time. In this paper, we extend the technique in [1] to the generalized problem of reporting many actual optimal paths with different starting and ending vertices in certain directed graphs. We show how this new technique yields improved results on several application problems, such as reconstructing a 3-D surface band bounded by two simple closed curves, finding various constrained segmentation of 2-D medical images, and circular string-to-string correction. Although the generalized many-path problem seems more difficult, our algorithms have nearly the same space and time bounds as those of the single-path cases. Our technique is likely to help improve other optimal paths or dynamic programming algorithms. We also correct an error in the time/space complexity for the circular string-to-string correction algorithm in [7] and give improved results for it.

In this paper we present an algorithm for enumerating without repetitions all non-crossing geometric spanning trees on a given set of points in the plane under edge inclusion constraints (i.e., some edges are required to be included in spanning trees). We will first prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the constrained smallest indexed triangulation which is obtained by extending the lexicographically ordered triangulation introduced by Bespamyatnikh. More specifically, we prove that all edge-constrained triangulations can be transformed to the smallest indexed triangulation among them by () times of greedy flips. Our enumeration algorithm generates each output graph in () time and () space based on reverse search technique.

We introduce the concept of as a generalization of simultaneous graph embeddings with and without mapping. We show that there exists a universal pointset of size for paths colored with two or three colors. We use these results to show that colored simultaneous geometric embeddings exist for: (1) a 2-colored tree together with any number of 2-colored paths and (2) a 2-colored outerplanar graph together with any number of 2-colored paths. We also show that there does not exist a universal pointset of size for paths colored with five colors. We finally show that the following simultaneous embeddings are not possible: (1) three 6-colored cycles, (2) four 6-colored paths, and (3) three 9-colored paths.

We formalize the definition of symmetric auctions to study fundamental properties of incentive compatible auction protocols. We characterize such auction protocols for those with a fixed number of items to sell and study some important properties of those with an indefinite number of sales.

We consider finding maximin strategies and equilibria of explicitly given extensive form games with imperfect information but with no moves of chance. We show that a maximin pure strategy for a two-player game with perfect recall and no moves of chance can be found in time linear in the size of the game tree and that all pure Nash equilibrium outcomes of a two-player general-sum game with perfect recall and no moves of chance can be enumerated in time linear in the size of the game tree. We also show that finding an optimal behavior strategy for a one-player game of no chance without perfect recall and determining whether an equilibrium in behavior strategies exists in a two-player zero-sum game of no chance without perfect recall are both -hard.

Each day a weather forecaster predicts a probability of each type of weather for the next day. After days, all the predicted probabilities and the real weather data are sent to a test which decides whether to accept the forecaster as possessing predicting power. Consider tests such that forecasters who know the distribution of nature are passed with high probability. Sandroni shows that any such test can be passed by a forecaster who has no prior knowledge of nature [San03], provided that the duration is known to the forecaster in advance. On the other hand, Fortnow and Vohra [FV06] show that Sandroni’s result may require forecasters with high computational complexity and is thus of little practical relevance in some cases. We consider forecasters who select a deterministic Turing-machine forecaster according to an arbitrary distribution and then use that machine for all future forecasts. We show that forecasters even more powerful than the above ones are required for Sandroni’s result. Also, we show that Sandroni’s result does not apply when the duration is not known to the forecaster in advance.

We introduce a new notion called that allows us to precisely characterize the class of Boolean functions for which a standard greedy learning algorithm successfully learns all relevant attributes. If the target function is Fourier-accessible, then the success probability of the greedy algorithm can be made arbitrarily close to one. On the other hand, if the target function is Fourier-accessible, then the error probability tends to one. Finally, we extend these results to the situation where the input data are corrupted by random attribute and classification noise and prove that greedy learning is quite robust against such errors.