Search

A key research interest in the area of Constraint Satisfaction Problems (CSP) is to identify tractable classes of constraints and develop efficient algorithms for solving them. In this paper, we propose an optimal algorithm for solving r-ary min-closed and max-closed constraints. Assuming r = O(1), our algorithm has an optimal running time of O(ct) where c and t are the number of constraints and the maximum size of any constraint, respectively. This significantly improves the existing pairwise consistency based algorithm that takes O(c2t2) time. Moreover, for (binary) connected row convex (CRC) constraints, we design an optimal algorithm for arc consistency that runs in O(cd) time where d is the largest size of any domain. This again improves upon the existing O(cd2) algorithms. This, in turn, leads to a faster algorithm for solving CRC constraints. We also show how our solutions can be applied to determine problems in large distributed IT systems. The experimental evaluation shows that the proposed algorithms are several orders of magnitudes faster than the state-of-the-art algorithms.

Facility location queries identify the best locations to set up new facilities for providing service to its users. Majority of the existing works in this space assume that the user locations are static. Such limitations are too restrictive for planning many modern real-life services such as fuel stations, ATMs, convenience stores, cellphone base-stations, etc. that are widely accessed by mobile users. The placement of such services should, therefore, factor in the mobility patterns or trajectories of the users rather than simply their static locations. In this work, we introduce the TOPS (Trajectory-Aware Optimal Placement of Services) query that locates the best k sites on a road network. The aim is to optimize a wide class of objective functions defined over the user trajectories. We show that the problem is NP-hard and even the greedy heuristic with an approximation bound of (1-1/e) fails to scale on urban-scale datasets. To overcome this challenge, we develop a multi-resolution clustering based indexing framework called NetClus. Empirical studies on real road network trajectory datasets show that NetClus offers solutions that are comparable in terms of quality with those of the greedy heuristic, while having practical response times and low memory footprints. Additionally, the NetClus framework can absorb dynamic updates in mobility patterns, handle constraints such as site-costs and capacity, and existing services, thereby providing an effective solution for modern urban-scale scenarios., Comment: ICDE 2017 poster

We design and evaluate algorithms for efficient user-mobility driven macro-cell planning in cellular networks. As cellular networks embrace heterogeneous technologies (including long range 3G/4G and short range WiFi, Femto-cells, etc.), most traffic generated by static users gets absorbed by the short-range technologies, thereby increasingly leaving mobile user traffic to macro-cells. To this end, we consider a novel approach that factors in the trajectories of mobile users as well as the impact of city geographies and their associated road networks for macro-cell planning. Given a budget k of base-stations that can be upgraded, our approach selects a deployment that impacts the most number of user trajectories. The generic formulation incorporates the notion of quality of service of a user trajectory as a parameter to allow different application-specific requirements, and operator choices.We show that the proposed trajectory utility maximization problem is NP-hard, and design multiple heuristics. We evaluate our algorithms with real and synthetic data sets emulating different city geographies to demonstrate their efficacy. For instance, with an upgrade budget k of 20%, our algorithms perform 3-8 times better in improving the user quality of service on trajectories in different city geographies when compared to greedy location-based base-station upgrades., Comment: Published in INFOCOM 2015

In this paper, we study the problem of effective route search in road networks. Given a pair of source and destination locations, the aim is to find a path from the source to the destination that visits k different types of sites in a particular order as prescribed by the user. The route planning problem has two objectives to optimize: minimize the total path length and maximize the probability of getting served from the k sites. Since the problem has a multi-objective nature, we utilize the skyline setting and retrieve all skyline paths according to the two aggregated attributes. The naive way of determining the path lengths can involve a large number of shortest path computations. Although the shortest paths between the sites can be pre-computed, the shortest paths from the source to the first type of site and those from the last type of site to the destination cannot be computed in an offline manner as the source and destination are arbitrary points that are available only at runtime. Similarly, the choice and order of the k different types of sites are also specified at runtime only. Since in a large road network, it is prohibitory to compute many shortest paths, we employ a heuristic to approximately solve the problem. The shortest path computation from the source to a site (and similarly, from a site to the destination) is approximated by introducing reference points. The reference points are chosen by employing a grid-based partitioning method on the space underlying the road network. We show that the above heuristic introduces only an additive error to the distance but not to the probability of service while reducing the running times by up to orders of magnitude.

We consider lifetime quality-of-experience (QoE) management for video-on-demand (VoD) users in WiMAX networks. For efficient resource utilization while enhancing user experience, we propose run-time load balancing through joint scheduling among multiple base stations (BSs), referred to as macro scheduling. Macro scheduling employs a utility-maximization approach. To achieve long-term proportional fairness (PF) and manage lifetime QoE, user and flow utilities are modeled as functions of their past service rates, in addition to current channel conditions and bandwidth needs. We show that scheduling flows across multiple BSs jointly to achieve PF is NP-hard in the strong sense. Since approximation algorithms proposed in prior work are computationally expensive for online use, we design efficient heuristics that perform as well as the approximation algorithms. A simulation-based evaluation shows that our overall macro scheduling scheme can improve the number of satisfied users by up to 35% in comparison to other approaches, while only minimally sacrificing on throughput.