ABSTRACT
Given a point set P of customers (e.g., WiFi receivers) and a point set Q of service providers (e.g., wireless access points), where each q ∈ Q has a capacity q.k, the capacity constrained assignment (CCA) is a matching M ⊆ Q × P such that (i) each point q ∈ Q (p ∈ P) appears at most k times (at most once) in M, (ii) the size of M is maximized (i.e., it comprises min{|P|, ∑q∈Qq.k} pairs), and (iii) the total assignment cost (i.e., the sum of Euclidean distances within all pairs) is minimized. Thus, the CCA problem is to identify the assignment with the optimal overall quality; intuitively, the quality of q's service to p in a given (q, p) pair is anti-proportional to their distance. Although max-flow algorithms are applicable to this problem, they require the complete distance-based bipartite graph between Q and P. For large spatial datasets, this graph is expensive to compute and it may be too large to fit in main memory. Motivated by this fact, we propose efficient algorithms for optimal assignment that employ novel edge-pruning strategies, based on the spatial properties of the problem. Additionally, we develop approximate (i.e., suboptimal) CCA solutions that provide a trade-off between result accuracy and computation cost, abiding by theoretical quality guarantees. A thorough experimental evaluation demonstrates the efficiency and practicality of the proposed techniques.
- R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, first edition, 1993. Google ScholarDigital Library
- N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In SIGMOD, 1990. Google ScholarDigital Library
- T. Brinkhoff. A Framework for Generating Network-Based Moving Objects. GeoInformatica, 6(2):153--180, 2002. Google ScholarDigital Library
- A. Corral, Y. Manolopoulos, Y. Theodoridis, and M. Vassilakopoulos. Closest Pair Queries in Spatial Databases. In SIGMOD, 2000. Google ScholarDigital Library
- A. V. Goldberg and R. Kennedy. An Efficient Cost Scaling Algorithm for the Assignment Problem. Mathematical Programming, 71:153--177, 1995. Google ScholarDigital Library
- A. Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD, 1984. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Distance Browsing in Spatial Databases. ACM Trans. Database Syst., 24(2):265--318, 1999. Google ScholarDigital Library
- J. Munkres. Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics, 5(1):32--38, 1957.Google ScholarCross Ref
- T. K. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In VLDB, 1987. Google ScholarDigital Library
- A. Silberschatz, H. F. Korth, and S. Sudarshan. Database System Concepts. McGraw-Hill, fifth edition, 2005. Google ScholarDigital Library
- I. H. Toroslu and G. Üçoluk. Incremental Assignment Problem. Inf. Sci., 177:1523--1529, 2007. Google ScholarDigital Library
- L. H. U, N. Mamoulis, and M. L. Yiu. Continuous Monitoring of Exclusive Closest Pairs. In SSTD, 2007.Google Scholar
- J. Vygen. Approximation Algorithms for Facility Location Problems (Lecture Notes). University of Bonn, 2004.Google Scholar
- R. C.-W. Wong, Y. Tao, A. Fu, and X. Xiao. On Efficient Spatial Matching. In VLDB, 2007. Google ScholarDigital Library
- M. L. Yiu and N. Mamoulis. Clustering objects on a spatial network. In SIGMOD, 2004. Google ScholarDigital Library
Index Terms
- Capacity constrained assignment in spatial databases
Recommendations
Optimal matching between spatial datasets under capacity constraints
Consider a set of customers (e.g., WiFi receivers) and a set of service providers (e.g., wireless access points), where each provider has a capacity and the quality of service offered to its customers is anti-proportional to their distance. The Capacity ...
Continuous spatial assignment of moving users
Consider a set of servers and a set of users, where each server has a coverage region (i.e., an area of service) and a capacity (i.e., a maximum number of users it can serve). Our task is to assign every user to one server subject to the coverage and ...
Addressing capacity uncertainty in resource-constrained assignment problems
Resource-constrained assignment problems typically assume capacities are known. We focus on the situation when capacities are uncertain. In addition to the well-known generalized assignment problem (GAP) and the assignment problem with side-constraints (...
Comments