Search Constraints
Number of results to display per page
Search Results

 Resource Type:
 Conference Proceeding
 Creator:
 Maheshwari, Anil, Nandy, Ayan, Smid, Michiel, and Das, Sandip
 Abstract:
 Consider a line segment R consisting of n facilities. Each facility is a point on R and it needs to be assigned exactly one of the colors from a given palette of c colors. At an instant of time only the facilities of one particular color are 'active' and all other facilities are 'dormant'. For the set of facilities of a particular color, we compute the one dimensional Voronoi diagram, and find the cell, i.e, a segment of maximum length. The users are assumed to be uniformly distributed over R and they travel to the nearest among the facilities of that particular color that is active. Our objective is to assign colors to the facilities in such a way that the length of the longest cell is minimized. We solve this optimization problem for various values of n and c. We propose an optimal coloring scheme for the number of facilities n being a multiple of c as well as for the general case where n is not a multiple of c. When n is a multiple of c, we compute an optimal scheme in Θ(n) time. For the general case, we propose a coloring scheme that returns the optimal in O(n2logn) time.
 Date Created:
 20140101

 Resource Type:
 Conference Proceeding
 Creator:
 Kim, SangWoon and Oommen, B. John
 Abstract:
 The Maximum Likelihood (ML) and Bayesian estimation paradigms work within the model that the data, from which the parameters are to be estimated, is treated as a set rather than as a sequence. The pioneering paper that dealt with the field of sequencebased estimation [2] involved utilizing both the information in the observations and in their sequence of appearance. The results of [2] introduced the concepts of Sequence Based Estimation (SBE) for the Binomial distribution, where the authors derived the corresponding MLE results when the samples are taken twoatatime, and then extended these for the cases when they are processed threeatatime, fouratatime etc. These results were generalized for the multinomial “twoatatime” scenario in [3]. This paper (This paper is dedicated to the memory of Dr. Mohamed Kamel, who was a close friend of the first author.) now further generalizes the results found in [3] for the multinomial case and for subsequences of length 3. The strategy used in [3] (and also here) involves a novel phenomenon called “Occlusion” that has not been reported in the field of estimation. The phenomenon can be described as follows: By occluding (hiding or concealing) certain observations, we map the estimation problem onto a lowerdimensional space, i.e., onto a binomial space. Once these occluded SBEs have been computed, the overall Multinomial SBE (MSBE) can be obtained by combining these lowerdimensional estimates. In each case, we formally prove and experimentally demonstrate the convergence of the corresponding estimates.
 Date Created:
 20160101

 Resource Type:
 Conference Proceeding
 Creator:
 Bertossi, Leopoldo
 Abstract:
 A correspondence between database tuples as causes for query answers in databases and tuplebased repairs of inconsistent databases with respect to denial constraints has already been established. In this work, answerset programs that specify repairs of databases are used as a basis for solving computational and reasoning problems about causes. Here, causes are also introduced at the attribute level by appealing to a both nullbased and attributebased repair semantics. The corresponding repair programs are presented, and they are used as a basis for computation and reasoning about attributelevel causes.
 Date Created:
 20180101

 Resource Type:
 Conference Proceeding
 Creator:
 Dujmović, Vida, De Carufel, JeanLou, Bose, Prosenjit, and Paradis, Frédérik
 Abstract:
 The wellseparated pair decomposition (WSPD) of the complete Euclidean graph defined on points in ℝ2 (Callahan and Kosaraju [JACM, 42 (1): 6790, 1995]) is a technique for partitioning the edges of the complete graph based on length into a linear number of sets. Among the many different applications of WSPDs, Callahan and Kosaraju proved that the sparse subgraph that results by selecting an arbitrary edge from each set (called WSPDspanner) is a 1 + 8/(s − 4)spanner, where s > 4 is the separation ratio used for partitioning the edges. Although competitive localrouting strategies exist for various spanners such as Yaographs, Θgraphs, and variants of Delaunay graphs, few localrouting strategies are known for any WSPDspanner. Our main contribution is a localrouting algorithm with a nearoptimal competitive routing ratio of 1 + O(1/s) on a WSPDspanner. Specifically, we present a 2local and a 1local routing algorithm on a WSPDspanner with competitive routing ratios of 1+6/(s−2)+4/s and 1+6/(s−2)+ 6/s + 4/(s2 − 2s) + 8/s2respectively.
 Date Created:
 20170101

 Resource Type:
 Conference Proceeding
 Creator:
 Lanthier, Mark, Velazquez, Elio, and Santoro, Nicola
 Abstract:
 This paper proposes a proactive solution to the Frugal Feeding Problem (FFP) in Wireless Sensor Networks. The FFP attempts to find energyefficient routes for a mobile service entity to rendezvous with each member of a team of mobile robots. Although the complexity of the FFP is similar to the Traveling Salesman Problem (TSP), we propose an efficient solution, completely distributed and localized for the case of a fixed rendezvous location (i.e., service facility with limited number of docking ports) and mobile capable entities (sensors). Our proactive solution reduces the FFP to finding energyefficient routes in a dynamic Compass Directed unit Graph (CDG). The proposed CDG incorporates ideas from forward progress routing and the directionality of compass routing in an energyaware unit subgraph. Navigating the CDG guarantees that each sensor will reach the rendezvous location in a finite number of steps. The ultimate goal of our solution is to achieve energy equilibrium (i.e., no further sensor losses due to energy starvation) by optimizing the use of the shared resource (recharge station). We also examine the impact of critical parameters such as transmission range, cost of mobility and sensor knowledge in the overall performance.
 Date Created:
 20111114

 Resource Type:
 Conference Proceeding
 Creator:
 Guo, Yuhong and Li, Xin
 Abstract:
 Multilabel classification is a central problem in many application domains. In this paper, we present a novel supervised bidirectional model that learns a lowdimensional midlevel representation for multilabel classification. Unlike traditional multilabel learning methods which identify intermediate representations from either the input space or the output space but not both, the midlevel representation in our model has two complementary parts that capture intrinsic information of the input data and the output labels respectively under the autoencoder principle while augmenting each other for the target output label prediction. The resulting optimization problem can be solved efficiently using an iterative procedure with alternating steps, while closedform solutions exist for one major step. Our experiments conducted on a variety of multilabel data sets demonstrate the efficacy of the proposed bidirectional representation learning model for multilabel classification.
 Date Created:
 20140101

 Resource Type:
 Conference Proceeding
 Creator:
 White, Anthony and SalehiAbari, Amirali
 Abstract:
 Autonomous agents require trust and reputation concepts in order to identify communities of agents with which to interact reliably in ways analogous to humans. Agent societies are invariably heterogeneous, with multiple decision making policies and actions governing their behaviour. Through the introduction of naive agents, this paper shows empirically that while learning agents can identify malicious agents through direct interaction, naive agents compromise utility through their inability to discern malicious agents. Moreover, the impact of the proportion of naive agents on the society is analyzed. The paper demonstrates that there is a need for witness interaction trust to detect naive agents in addition to the need for direct interaction trust to detect malicious agents. By proposing a set of policies, the paper demonstrates how learning agents can isolate themselves from naive and malicious agents.
 Date Created:
 20100720

 Resource Type:
 Conference Proceeding
 Creator:
 Prencipe, Giuseppe, Cáceres, Edson, Chan, Albert, and Dehne, Frank
 Abstract:
 In this paper, we present parallel algorithms for the coarse grained multicomputer (CGM) and the bulk synchronous parallel computer (BSP) for solving two well known graph problems: (1) determining whether a graph G is bipartite, and (2) determining whether a bipartite graph G is convex. Our algorithms require O(log p) and O(log2 p) communication rounds, respectively, and linear sequential work per round on a CGM with p processors and N/p local memory per processor, N=G. The algorithms assume that N/ p ≥ p€ for some fixed€ > 0, which is true for all commercially available multiprocessors. Our results imply BSP algorithms with O(log p) and O(log2 p) supersteps, respectively, O(g log(p) N p) communication time, and O(log(p) N p) local computation time. Our algorithm for determining whether a bipartite graph is convex includes a novel, coarse grained parallel, version of the PQ tree data structure introduced by Booth and Lueker. Hence, our algorithm also solves, with the same time complexity as indicated above, the problem of testing the consecutiveones property for (0, 1) matrices as well as the chordal graph recognition problem. These, in turn, have numerous applications in graph theory, DNA sequence assembly, database theory, and other areas.
 Date Created:
 20000101

 Resource Type:
 Conference Proceeding
 Creator:
 Maheshwari, Anil and Zeh, Norbert
 Abstract:
 We present external memory algorithms for outerplanarity testing, embedding outerplanar graphs, breadthfirst search (BFS) and depthfirst search (DFS) in outerplanar graphs, and finding a2separator of size 2 for a given outerplanar graph. Our algorithms take O(sort(N)) I/Os and can easily be improved to take O (perm (N)) I/Os, as all these problems have linear time solutions in internal memory. For BFS, DFS, and outerplanar embedding we show matching lower bounds.
 Date Created:
 19990101

 Resource Type:
 Conference Proceeding
 Creator:
 Morin, Pat and Bose, Prosenjit
 Abstract:
 We consider online routing strategies for routing between the vertices of embedded planar straight line graphs. Our results include (1) two deterministic memoryless routing strategies, one that works for all Delaunay triangulations and the other that works for all regular triangulations, (2) a randomized memoryless strategy that works for all triangulations, (3) an O(1) memory strategy that works for all convex subdivisions, (4) an O(1) memory strategy that approximates the shortest path in Delaunay triangulations, and (5) theoretical and experimental results on the competitiveness of these strategies.
 Date Created:
 19990101