Budget-Constrained Cost-Covering Job Assignment for a Total Contribution-Maximizing Platform
學年 111
學期 2
發表日期 2023-06-07
作品名稱 Budget-Constrained Cost-Covering Job Assignment for a Total Contribution-Maximizing Platform
作品名稱（其他語言）
著者 Chi-Hao Wang; Chi-Jen Lu; Ming-Tat Ko; Po-An Chen and Chuang-Chieh Lin
作品所屬單位
出版者
會議名稱 International Workshop on Combinatorial Algorithms (IWOCA 2023)
會議地點 Tainan, Taiwan
摘要 We propose an optimization problem to model a situation when a platform with a limited budget wants to pay a group of workers to work on a set of jobs with possibly worker-job-dependent execution costs. The platform needs to assign workers to jobs and at the same time decides how much to pay each worker to maximize the total “contribution” from the workers by using up the limited budget. The binary effort assignment problem, in which an effort from a worker is indivisible and can only be dedicated to a single job, is reminiscent of bipartite matching problems. Yet, a matched worker and job pair neither incurs cost nor enforces a compulsory effort in a standard matching setting while we consider such cost to be covered by payment and certain level of effort to be made when a job is executed by a worker. The fractional effort assignment problem, in which generally a worker’s effort can be divisible and split among multiple jobs, bears a resemblance to a labor economy or online labor platform, and the platform needs to output an arrangement of efforts and the corresponding payments. There are six settings in total to consider by combining the conditions on payments and efforts. Intuitively, we study how to come up with the best assignment under each setting and how different these assignments under different settings can be in terms of the total contribution from workers when the information of each worker’s quality of service and cost is available. NP-completeness results and approximation algorithms are given for different settings. We then compare the solution quality of some settings in the end.
關鍵字 Job Assignment;Budget Constraint;Cost Covering;Contribution Maximization
語言 en
收錄於
會議性質 國際
校內研討會地點 無
研討會時間 20230607~20230610
通訊作者 Po-An Chen
國別 TWN
公開徵稿
出版型式
出處 34th Proceedings of the International Workshop on Combinatorial Algorithms
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/124082 )

SDGS 優質教育