8542665
Polynomial time approximation schemes and parameterized complexity
In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes.
16331940
Optimal Parallel Routing in Star Networks
Star networks have recently been proposed as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. In this paper, we present an efficient algorithm that constructs an optimal parallel routing in star networks. Our result improves previous results for the problem.
31382426
Strong Fault-Tolerance: Parallel Routing in Networks with Faults
A d-regular network G is strongly fault-tolerant if for any copy Gf of G with at most d - 2 faulty nodes, every pair of nonfaulty nodes u and v in Gf admits min{df(u), df (v)} node-disjoint paths in Gf from u to v, where df(u) and df(v) are the degrees of the nodes u and v in Gf. We show that popular network structures, such as hypercube and star networks, are strongly fault-tolerant. We develop efficient algorithms that construct the maximum number of node-disjoint paths of optimal or nearly optimal length in these networks with faulty nodes. Our algorithms are optimal in terms of their running time.
5242879
Interactive rind modeling
In this paper, we describe a technique, with roots in topological graph theory, that we call rind modeling. It provides for the easy creation of surfaces resembling peeled and punctured rinds. We show how the method's two main steps of: 1) creation of a shell or crust like the rind of an orange, and 2) opening holes in the crust by punching or peeling can be encapsulated into a real time semi-automatic interactive algorithm. We include a number of worked examples, some by students in a first modeling course, that demonstrate the ease with which a large variety of intricate rind shapes can be created.
2261180
Graph Ear Decompositions and Graph Embeddings
Ear decomposition of a graph has been extensively studied in relation to graph connectivity. In this paper, a connection of ear decomposition to graph embeddings is exhibited. It is shown that constructing a maximum-paired ear decomposition of a graph and constructing a maximum-genus embedding of the graph are polynomial-time equivalent. Applications of this connection are discussed.
1021255
A minimal and complete set of operators for the development of robust manifold mesh modelers
In this paper, we identify a minimal and complete set of fundamental operators, which is necessary and sufficient for performing all homeomorphic and topological operations on 2- manifold mesh structures. Efficient algorithms are developed for the implementation of these operators. We also developed a set of powerful, user-friendly, and effective operators at the level of user-interface. Using these operators, we have developed a prototype system for robust, interactive, and user-friendly modeling of orientable 2-manifold meshes. Users of our system can perform a large set of homeomorphic and topological changes with these user-interface level operators. Our system is topologically robust in the sense that users will never create invalid 2-manifold mesh structure with these operators. In our system, the homeomorphic and topological surgery operations can be applied alternatively on 2-manifold meshes. With our system, users can blend surfaces, construct rinds, and open holes on these rind shapes. With our system, the shapes that look like solid, non-manifold, or 2-manifold with boundary can be manipulated. The system also provides automatic texture mapping during topology changes.
6192242
Computing Maximum-Scoring Segments in Almost Linear Time
Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function.
43754145
Heaps with Bits
In this paper, we show how to improve the complexity of heap operations and heapsort using extra bits. We first study parallel complexity of implementing priority queue operations on a heap. While the insertion of a new element into a heap can be done as fast as parallel searching, we show how to delete the smallest element from a heap in constant time with a sublinear number of processors, and in sublogarithmic time with a sublogarithmic number of processors. The models of parallel computation used are the CREW PRAM and the CRCW PRAM. Our results improve those of previously known algorithms.
13718639
Designing online auctions with past performance information
We investigate the value of past performance information in the context of keyword advertising auctions, where advertisers differ both in valuation-per-click and in the numbers of clicks they can generate (their performance). We focus on weighted unit-price-contract (UPC) auctions, in which bidders bid unit prices and pay accordingly if they win, and their bids are weighted by factors based on their own past performance. We characterize the efficient and the revenue-maximizing weighting factors and apply our framework to study Yahoo!'s and Google's auction designs, each of which can be viewed as a special case of weighted UPC auctions.
3146872
Towards Automatic Generation of Natural Language Generation Systems
Systems that interact with the user via natural language are in their infancy. As these systems mature and become more complex, it would be desirable for a system developer if there were an automatic method for creating natural language generation components that can produce quality output efficiently. We conduct experiments that show that this goal appears to be realizable. In particular we discuss a natural language generation system that is composed of SPoT, a trainable sentence planner, and FER-GUS, a stochastic surface, realizer. We show how these stochastic NLG components can be made to work together, that they can be ported to new domains with apparent ease, and that such NLG components can be integrated in a real-time dialog system.
10702245
A wireless LAN-based indoor positioning technology
Context-aware computing is an emerging computing paradigm that can provide new or improved services by exploiting user context information. In this paper, we present a wireless-local-area-network-based (WLAN-based) indoor positioning technology. The wireless device deploys a position-determination model to gather location information from collected WLAN signals. A model-based signal distribution training scheme is proposed to trade off the accuracy of signal distribution and training workload. A tracking-assistant positioning algorithm is presented to employ knowledge of the area topology to assist the procedure of position determination. We have set up a positioning system at the IBM China Research Laboratory. Our experimental results indicate an accuracy of 2 m with a 90% probability for static devices and, for moving (walking) devices, an accuracy of 5 m with a 90% probability. Moreover, the complexity of the training procedure is greatly reduced compared with other positioning algorithms.