會議論文
| 學年 | 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 ) |