{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T04:10:10Z","timestamp":1751861410503,"version":"3.41.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T00:00:00Z","timestamp":1736553600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T00:00:00Z","timestamp":1736553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["SPR\/2021\/000860","SPR\/2021\/000860","SPR\/2021\/000860"],"award-info":[{"award-number":["SPR\/2021\/000860","SPR\/2021\/000860","SPR\/2021\/000860"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Indian Institite of Technology Jodhpur","award":["I\/SEED\/PJ\/20210119"],"award-info":[{"award-number":["I\/SEED\/PJ\/20210119"]}]},{"name":"Institute of Mathematical Sciences"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s10458-024-09686-1","type":"journal-article","created":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T08:53:02Z","timestamp":1736585582000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Budget-feasible egalitarian allocation of conflicting jobs"],"prefix":"10.1007","volume":"39","author":[{"given":"Sushmita","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Pallavi","family":"Jain","sequence":"additional","affiliation":[]},{"given":"A.","family":"Mohanapriya","sequence":"additional","affiliation":[]},{"given":"Vikash","family":"Tripathi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,11]]},"reference":[{"key":"9686_CR1","first-page":"101","volume":"16","author":"H Steinhaus","year":"1948","unstructured":"Steinhaus, H. (1948). The problem of fair division. Econometrica, 16, 101\u2013104.","journal-title":"Econometrica"},{"issue":"5","key":"9686_CR2","first-page":"1","volume":"85","author":"N Chiarelli","year":"2022","unstructured":"Chiarelli, N., Krnc, M., Milani\u010d, M., Pferschy, U., Piva\u010d, N., & Schauer, J. (2022). Fair allocation of indivisible items with conflict graphs. Algorithmica, 85(5), 1\u201331.","journal-title":"Algorithmica"},{"key":"9686_CR3","unstructured":"Biswas, A., Ke, Y., Khuller, S. & Liu QC. (2023). An Algorithmic Approach to Address Course Enrollment Challenges. In: 4th Symposium on Foundations of Responsible Computing, FORC 2023, 256 of LIPIcs. p. 8:1\u20138:23."},{"issue":"1","key":"9686_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10458-021-09537-3","volume":"36","author":"H Hummel","year":"2022","unstructured":"Hummel, H., & Hetland, M. L. (2022). Fair allocation of conflicting items. Autonomous Agents and Multi-Agent Systems., 36(1), 1\u201333.","journal-title":"Autonomous Agents and Multi-Agent Systems."},{"key":"9686_CR5","doi-asserted-by":"crossref","unstructured":"Garg, J., Hoefer, M. & Mehlhorn, K. (2018). Approximating the Nash Social Welfare with Budget-Additive Valuations. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). p. 2326-2340.","DOI":"10.1137\/1.9781611975031.150"},{"key":"9686_CR6","doi-asserted-by":"crossref","unstructured":"Barman, S., Khan, A., Shyam, S. & Sreenivas KVN. (2023). Finding Fair Allocations under Budget Constraints. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI). p. 5481\u20135489.","DOI":"10.1609\/aaai.v37i5.25681"},{"key":"9686_CR7","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Eiben, E., Ganian, R., Hamm, T. & Ordyniak S. (2021). The Parameterized Complexity of Connected Fair Division. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI); p. 139\u2013145.","DOI":"10.24963\/ijcai.2021\/20"},{"key":"9686_CR8","doi-asserted-by":"crossref","unstructured":"Madathil, J. (2023). Fair Division of a Graph into Compact Bundles. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, (IJCAI) 2023, 19th-25th August 2023, Macao, SAR, China; p. 2835\u20132843.","DOI":"10.24963\/ijcai.2023\/316"},{"key":"9686_CR9","unstructured":"Dippel, J., la\u00a0Tour MD, Niu, A., Roy, S. & Vetta, A. (2023). Gerrymandering Planar Graphs. CoRR. abs\/2312.14721."},{"key":"9686_CR10","unstructured":"Garey, MR. & Johnson, DS. (1979). Computers and intractability. vol. 174. freeman."},{"key":"9686_CR11","doi-asserted-by":"crossref","unstructured":"Bansal, N. & Sviridenko, M. (2006). The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC); p. 31\u201340.","DOI":"10.1145\/1132516.1132522"},{"key":"9686_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, FV., Kowalik, Lu., Lokshtanov, D., Marx, D., Pilipczuk, M., et\u00a0al. (2015). Parameterized algorithms. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"9686_CR13","first-page":"1","volume-title":"Mao, Y","author":"S Cheng","year":"2022","unstructured":"Cheng, S. (2022). Mao, Y (pp. 1\u201340). Restricted Max-Min Allocation: Integrality Gap and Approximation Algorithm. Algorithmica."},{"issue":"3","key":"9686_CR14","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1120680.1120683","volume":"5","author":"I Bez\u00e1kov\u00e1","year":"2005","unstructured":"Bez\u00e1kov\u00e1, I., & Dani, V. (2005). Allocating indivisible goods. ACM SIGecom Exchanges., 5(3), 11\u201318.","journal-title":"ACM SIGecom Exchanges."},{"issue":"2","key":"9686_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3140756","volume":"65","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa, D., Procaccia, A. D., & Wang, J. (2018). Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM (JACM)., 65(2), 1\u201327.","journal-title":"Journal of the ACM (JACM)."},{"key":"9686_CR16","unstructured":"Ebadian, S., Peters, D. & Shah, N. (2022). How to Fairly Allocate Easy and Difficult Chores. In: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS); p. 372\u2013380."},{"key":"9686_CR17","unstructured":"Barman, S. & Verma, P. (2021). Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations. In: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS); p. 169-177."},{"issue":"2","key":"9686_CR18","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/j.ejor.2021.03.026","volume":"295","author":"MM Ahmadian","year":"2021","unstructured":"Ahmadian, M. M., Khatami, M., Salehipour, A., & Cheng, T. C. E. (2021). Four decades of research on the open-shop scheduling problem to minimize the makespan. European Journal of Operational Research, 295(2), 399\u2013426.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"9686_CR19","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/3505156.3505162","volume":"19","author":"W Suksompong","year":"2021","unstructured":"Suksompong, W. (2021). Constraints in fair division. ACM SIGecom Exchanges, 19(2), 46\u201361.","journal-title":"ACM SIGecom Exchanges"},{"issue":"4","key":"9686_CR20","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0167-6377(96)00055-7","volume":"20","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G. J. (1997). A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4), 149\u2013154.","journal-title":"Operations Research Letters"},{"issue":"2","key":"9686_CR21","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1137\/0603019","volume":"3","author":"BL Deuermeyer","year":"1982","unstructured":"Deuermeyer, B. L., Friesen, D. K., & Langston, M. A. (1982). Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM Journal on Algebraic Discrete Methods, 3(2), 190\u2013196.","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"issue":"2","key":"9686_CR22","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy, U., & Schauer, J. (2009). The knapsack problem with conflict graphs. Journal of Graph Algorithms and Applications, 13(2), 233\u2013249.","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"4","key":"9686_CR23","doi-asserted-by":"publisher","first-page":"1300","DOI":"10.1007\/s10878-016-0035-7","volume":"33","author":"U Pferschy","year":"2017","unstructured":"Pferschy, U., & Schauer, J. (2017). Approximation of knapsack problems with conflict and forcing graphs. Journal of Combinatorial Optimization, 33(4), 1300\u20131323.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"9686_CR24","doi-asserted-by":"publisher","first-page":"1270","DOI":"10.1137\/060666329","volume":"19","author":"L Epstein","year":"2008","unstructured":"Epstein, L., & Levin, A. (2008). On bin packing with conflicts. SIAM Journal on Optimization, 19(3), 1270\u20131298.","journal-title":"SIAM Journal on Optimization"},{"key":"9686_CR25","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A. & Peters, D. (2017). Fair Division of a Graph. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI); p. 135\u2013141.","DOI":"10.24963\/ijcai.2017\/20"},{"issue":"16","key":"9686_CR26","doi-asserted-by":"publisher","first-page":"1726","DOI":"10.1016\/j.dam.2010.12.016","volume":"159","author":"A Darmann","year":"2011","unstructured":"Darmann, A., Pferschy, U., Schauer, J., & Woeginger, G. J. (2011). Paths, trees and matchings under disjunctive constraints. Discrete Applied Mathematics, 159(16), 1726\u20131735.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"9686_CR27","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G Even","year":"2009","unstructured":"Even, G., Halld\u00f3rsson, M. M., Kaplan, L., & Ron, D. (2009). Scheduling with conflicts: Online and offline algorithms. Journal of Scheduling, 12(2), 199\u2013224.","journal-title":"Journal of Scheduling"},{"key":"9686_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2019.104805","volume":"113","author":"P Factorovich","year":"2020","unstructured":"Factorovich, P., M\u00e9ndez-D\u00edaz, I., & Zabala, P. (2020). Pickup and delivery problem with incompatibility constraints. Computers & Operations Research, 113, 104805.","journal-title":"Computers & Operations Research"},{"key":"9686_CR29","doi-asserted-by":"crossref","unstructured":"Coffman\u00a0Jr, EG., Csirik, J., Galambos, G., Martello, S. & Vigo, D. (2013). In: Pardalos PM, Du DZ, Graham RL, (Eds.) Bin Packing Approximation Algorithms: Survey and Classification. Springer. Berlin Heidelberg p. 455\u2013531.","DOI":"10.1007\/978-1-4419-7997-1_35"},{"key":"9686_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin Heidelberg: Springer-Verlag."},{"key":"9686_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2023.103965","volume":"322","author":"G Amanatidis","year":"2023","unstructured":"Amanatidis, G., Aziz, H., Birmpas, G., Filos-Ratsikas, A., Li, B., Moulin, H., et al. (2023). Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence., 322, 103965.","journal-title":"Artificial Intelligence."},{"key":"9686_CR32","unstructured":"Diestel, R. (2012). Graph Theory, 4th Edition. vol. 173 of Graduate texts in mathematics. Springer."},{"key":"9686_CR33","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized Complexity Theory. Berlin heidelberg: Springer-Verlag."},{"key":"9686_CR34","volume-title":"Fellows MR","author":"RG Downey","year":"2013","unstructured":"Downey, R. G. (2013). Fellows MR. Berlin Heidelberg: Fundamentals of parameterized complexity. Texts in Computer Science. Springer."},{"key":"9686_CR35","doi-asserted-by":"crossref","unstructured":"Blair, JRS., Peyton, B. (1993). An introduction to chordal graphs and clique trees. In: Graph theory and sparse matrix computation. vol.\u00a056 of IMA Vol. Math. Appl. Springer. p. 1\u201329.","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"9686_CR36","doi-asserted-by":"crossref","unstructured":"Spinrad, JP. (2003). Efficient Graph Representations.: The Fields Institute for Research in Mathematical Sciences. American Mathematical Society. 19.","DOI":"10.1090\/fim\/019"},{"key":"9686_CR37","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/B978-0-12-289260-8.50011-X","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M. C. (1980). CHAPTER 4 - Triangulated Graphs. In M. C. Golumbic (Ed.), Algorithmic Graph Theory and Perfect Graphs (pp. 81\u2013104). Academic Press."},{"key":"9686_CR38","doi-asserted-by":"crossref","unstructured":"Moenck, RT. (1976). Practical fast polynomial multiplication. In: Proceedings of Symposium on Symbolic and Algebraic Computation (SYMSAC)\u201976; p. 136\u2013148.","DOI":"10.1145\/800205.806332"},{"key":"9686_CR39","doi-asserted-by":"crossref","unstructured":"Gupta, S., Jain, P., Saurabh, S. & Talmon, N. (2020). Well-Structured Committee. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI); p. 189\u2013195.","DOI":"10.24963\/ijcai.2020\/27"},{"key":"9686_CR40","doi-asserted-by":"crossref","unstructured":"Gupta, S., Jain, P. & Seetharaman, S. (2023). More Effort Towards Multiagent Knapsack. In: SOFSEM 2023: Theory and Practice of Computer Science: 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Nov\u00fd Smokovec, Slovakia, January 15-18, Proceedings; 2023. p. 47-62.","DOI":"10.1007\/978-3-031-23101-8_4"},{"issue":"40","key":"9686_CR41","doi-asserted-by":"publisher","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M Cygan","year":"2010","unstructured":"Cygan, M., & Pilipczuk, M. (2010). Exact and approximate bandwidth. Theoretical Computer Science., 411(40), 3701\u20133713.","journal-title":"Theoretical Computer Science."},{"issue":"4","key":"9686_CR42","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., & Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences., 63(4), 512\u2013530.","journal-title":"Journal of Computer and System Sciences."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09686-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-024-09686-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09686-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T03:53:38Z","timestamp":1751860418000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-024-09686-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,11]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["9686"],"URL":"https:\/\/doi.org\/10.1007\/s10458-024-09686-1","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2025,1,11]]},"assertion":[{"value":"31 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"6"}}