Fair Surveillance Assignment Problem
Authors: 
Fangxiao Wang, Bo LiAuthors Info & Claims
Pages 178 - 186
Abstract
Monitoring a specific set of locations serves multiple purposes, such as infrastructure inspection and safety surveillance. We study a generalization of the surveillance problem, where the monitoring area, represented by a graph, is divided and assigned to a set of agents with personalized cost functions. In this paper, each agent's patrolling cost towards receiving a subgraph is measured by the weight of the minimum vertex cover therein, and our objective is to design algorithms to compute fair assignments of the surveillance tasks. The fairness is assessed using maximin share (MMS) fairness proposed by Budish [J. Political Econ., 2011]. Our main result is an algorithm which ensures a 4.562-approximate MMS allocation for any number of agents with arbitrary vertex weights. We then prove that no algorithm can be better than 2-approximate MMS. For scenarios involving no more than four agents, we improve the approximation ratio to 2, which is thus the optimal achievable ratio.
Supplemental Material
MP4 File
Supplemental video
- Download
- 4.62 MB
References
[1]
Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. 2020. Fair clustering via equitable group representations. CoRR, Vol. abs/2006.11009 (2020).
[2]
Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. 2023. Fair division of indivisible goods: Recent progress and open questions. Artif. Intell., Vol. 322 (2023), 103965.
[3]
Esther M. Arkin, Refael Hassin, and Asaf Levin. 2006. Approximations for minimum and min-max vehicle routing problems. J. Algorithms, Vol. 59, 1 (2006), 1--18.
[4]
Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. 2021. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In APPROX-RANDOM (LIPIcs, Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum fü r Informatik, 1:1--1:23.
[5]
Eric Budish. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, Vol. 119, 6 (2011), 1061--1103.
[6]
Aydin Bulucc, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2016. Recent Advances in Graph Partitioning. In Algorithm Engineering. Lecture Notes in Computer Science, Vol. 9220. 117--158.
[7]
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The Unreasonable Fairness of Maximum Nash Welfare. ACM Trans. Economics and Comput., Vol. 7, 3 (2019), 12:1--12:32.
[8]
Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. 2021. A Little Charity Guarantees Almost Envy-Freeness. SIAM J. Comput., Vol. 50, 4 (2021), 1336--1358.
[9]
Zheng Chen, Bo Li, Minming Li, and Guochuan Zhang. 2022. Fair Graphical Resource Allocation with Matching-Induced Utilities. CoRR, Vol. abs/2212.01031 (2022).
[10]
Eden Chlamtá c, Yury Makarychev, and Ali Vakilian. 2022. Approximating Fair Clustering with Cascaded Norm Objectives. In SODA. SIAM, 2664--2683.
[11]
Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. 2021. Keep Your Distance: Land Division With Separation. In IJCAI. ijcai.org, 168--174.
[12]
Leah Epstein, Asaf Levin, and Gerhard J. Woeginger. 2016. Vertex Cover Meets Scheduling. Algorithmica, Vol. 74, 3 (2016), 1148--1173.
[13]
Guy Even, Naveen Garg, Jochen Kö nemann, R. Ravi, and Amitabh Sinha. 2004. Min-max tree covers of graphs. Oper. Res. Lett., Vol. 32, 4 (2004), 309--315.
[14]
Boaz Farbstein and Asaf Levin. 2015. Min-max cover of a graph with a small number of parts. Discret. Optim., Vol. 16 (2015), 51--61.
[15]
George Gamow and Marvin Stern. 1958. Puzzle-Math. Viking press.
[16]
Jugal Garg and Setareh Taki. 2021. An improved approximation algorithm for maximin shares. Artif. Intell., Vol. 300 (2021), 103547.
[17]
Laurent Gourvè s, Jé rô me Monnot, and Lydia Tlilane. 2014. Near Fairness in Matroids. In ECAI (Frontiers in Artificial Intelligence and Applications, Vol. 263). IOS Press, 393--398.
[18]
Hadi Hosseini, Andrew McGregor, Rik Sengupta, Rohit Vaish, and Vignesh Viswanathan. 2023 a. Tight Approximations for Graphical House Allocation. CoRR, Vol. abs/2307.12482 (2023).
[19]
Hadi Hosseini, Shivika Narang, and Tomasz Was. 2023 b. Fair Distribution of Delivery Orders. CoRR, Vol. abs/2305.00040 (2023).
[20]
Xin Huang and Pinyan Lu. 2021. An Algorithmic Framework for Approximating Maximin Share Allocation of Chores. In EC. ACM, 630--631.
[21]
Satoru Iwata and R. Ravi. 2013. Approximating max-min weighted T-joins. Oper. Res. Lett., Vol. 41, 4 (2013), 321--324.
[22]
M. Reza Khani and Mohammad R. Salavatipour. 2014. Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems. Algorithmica, Vol. 69, 2 (2014), 443--460.
[23]
cC agri Kocc, Tolga Bektas, Ola Jabali, and Gilbert Laporte. 2016. Thirty years of heterogeneous vehicle routing. Eur. J. Oper. Res., Vol. 249, 1 (2016), 1--21.
[24]
Dominik Kress, Sebastian Meiswinkel, and Erwin Pesch. 2015. The Partitioning Min-Max Weighted Matching Problem. Eur. J. Oper. Res., Vol. 247, 3 (2015), 745--754.
[25]
Bo Li, Fangxiao Wang, and Yu Zhou. 2023. Fair Allocation of Indivisible Chores: Beyond Additive Costs. In NeurIPS 2023. (to appear).
[26]
Michael Lin and Richard J. La. 2020. Miniature Robot Path Planning for Bridge Inspection: Min-Max Cycle Cover-Based Approach. In CASE. IEEE, 365--371.
[27]
Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In EC. ACM, 125--131.
[28]
Yury Makarychev and Ali Vakilian. 2021. Approximation Algorithms for Socially Fair Clustering. CoRR, Vol. abs/2103.02512 (2021).
[29]
Flá vio Keidi Miyazawa, Phablo F. S. Moura, Matheus J. Ota, and Yoshiko Wakabayashi. 2021. Partitioning a graph into balanced connected classes: Formulations, separation and experiments. Eur. J. Oper. Res., Vol. 293, 3 (2021), 826--836.
[30]
Benjamin Plaut and Tim Roughgarden. 2020. Almost Envy-Freeness with General Valuations. SIAM J. Discret. Math., Vol. 34, 2 (2020), 1039--1068.
[31]
Hugo Steinhaus. 1949. Sur la division pragmatique. Econometrica, Vol. 17 (Supplement) (1949), 315--319.
[32]
Vera Traub and Thorben Trö bst. 2020. A Fast (2 2/7)-Approximation Algorithm for Capacitated Cycle Covering. In IPCO. Springer, 391--404.
[33]
Hal R. Varian. 1974. Equity, Envy and Efficiency. Journal of Economic Theory, Vol. 9 (1974), 63--91.
[34]
Zhenbo Wang and Zhenhua Cui. 2012. Combination of parallel machine scheduling and vertex cover. Theor. Comput. Sci., Vol. 460 (2012), 10--15.
[35]
Zhou Xu and Qi Wen. 2010. Approximation hardness of min-max tree covers. Oper. Res. Lett., Vol. 38, 3 (2010), 169--173.
[36]
Hande Yaman. 2006. Formulations and Valid Inequalities for the Heterogeneous Vehicle Routing Problem. Math. Program., Vol. 106, 2 (2006), 365--390.
[37]
Shengwei Zhou and Xiaowei Wu. 2022. Approximately EFX Allocations for Indivisible Chores. In IJCAI. ijcai.org, 783--789.
Index Terms
- Fair Surveillance Assignment Problem
Recommendations
Equitable Allocations of Indivisible Chores
AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent SystemsWe study fair allocation of indivisible chores (i.e., items with non-positive value) among agents with additive valuations. An allocation is deemed fair if it is (approximately) equitable, which means that the disutilities of the agents are (...
Fairness criteria for allocating indivisible chores: connections and efficiencies
AbstractWe study several fairness notions in allocating indivisible chores (i.e., items with disutilities) to agents who have additive and submodular cost functions. The fairness criteria we are concerned with are envy-free up to any item, envy-free up to ...
Price of Connectivity for the Vertex Cover Problem and the Dominating Set Problem: Conjectures and Investigation of Critical Graphs
The vertex cover problem and the dominating set problem are two well-known problems in graph theory. Their goal is to find the minimum size of a vertex subset satisfying some properties. Both hold a connected version, which imposes that the vertex ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
4826 pages
ISBN:9798400701719
DOI:10.1145/3589334
- General Chairs:
- Tat-Seng Chua,
- Chong-Wah Ngo,
- Proceedings Chair:
- Roy Ka-Wei Lee,
- Program Chairs:
- Ravi Kumar,
- Hady W. Lauw
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
WWW '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,899 of 8,196 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 202Total Downloads
- Downloads (Last 12 months)202
- Downloads (Last 6 weeks)28
Reflects downloads up to 07 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in