General Assignment Problems

Title: Generalized Assignment Problem: Truthful Mechanism Design without Money

Authors:Salman Fadaei, Martin Bichler

(Submitted on 15 Aug 2016 (v1), last revised 15 Jan 2017 (this version, v3))

Abstract: In this paper, we study a problem of truthful mechanism design for a strategic variant of the generalized assignment problem (GAP) in a both payment-free and prior-free environment. In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity of any singular bin. In the strategic variant of the problem we study, bins are held by strategic agents, and each agent may hide its compatibility with some items in order to obtain items of higher values. The compatibility between an agent and an item encodes the willingness of the agent to receive the item. Our goal is to maximize total value (sum of agents' values, or social welfare) while certifying no agent can benefit from hiding its compatibility with items. The model has applications in auctions with budgeted bidders. For two variants of the problem, namely \emph{multiple knapsack problem} in which each item has the same size and value over bins, and \emph{density-invariant GAP} in which each item has the same value density over the bins, we propose truthful $4$-approximation algorithms. For the general problem, we propose an $O(\ln{(U/L)})$-approximation mechanism where $U$ and $L$ are the upper and lower bounds for value densities of the compatible item-bin pairs.

Submission history

From: Salman Fadaei [view email]
[v1] Mon, 15 Aug 2016 14:11:02 GMT (23kb)
[v2] Tue, 23 Aug 2016 05:12:49 GMT (21kb)
[v3] Sun, 15 Jan 2017 21:01:12 GMT (19kb)

Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

  • Amini, M.M. and M. Racer. (1994). “A Rigorous Comparison of Alternative Solution Methods for the Generalized Assignment Problem.” Management Science 40, 868–890.Google Scholar

  • Beale, E.M.L. and J.J.H. Forrest. (1976). “Global Optimization Using Special Ordered Sets.” Mathematical Programming 10, 52–69.CrossRefGoogle Scholar

  • Beasley, J.E. (1990). “OR-Library: Distributing Test Problems by Electronic Mail. ” Journal of the Operational Research Society 41, 1069–1072.Google Scholar

  • Beale, E.M.L. and J.A. Tomlin. (1970). “Special Facilities in a General Mathematical Programming System for Non-Convex Problems Using Ordered Sets of Variables.” In J. Lawrence (ed.), OR 69: Proceedings of the Fifth International Conference on Operational Research, Venice 1969. London: Tavistock Publications, pp. 447–454.Google Scholar

  • Cattrysse, D., Z. Degraeve, and J. Tistaert. (1998). “Solving the Generalized Assignment Problem Using Polyhedral Results.” European Journal of Operational Research 108, 618–628.CrossRefGoogle Scholar

  • Chu, P.C. and J.E. Beasley. (1997). “A Genetic Algorithm for the Generalized Assignment Problem.” Computers and Operations Research 24, 260–272.CrossRefGoogle Scholar

  • de Farias Jr, I.R., E.L. Johnson, and G.L. Nemhauser. (2000). “A Generalized Assigment Problem with Special Odered Sets: A Polyhedral Approach.” Mathematical Programming 89, 187–203.Google Scholar

  • Diaz, J.A. and E. Fernandez. (2001). “A Tabu Search Heuristic for the Generalized Assignment Problem.” European Journal of Operational Research132, 22–38.CrossRefMathSciNetGoogle Scholar

  • M.L. Fisher, R. Jaikamur, and L.N. Van Wassenhove. (1986). “A Multiplier Adjustment Method for the Generalized Assignment Problem.” Management Science 32, 1095–1103.Google Scholar

  • Guignard, M.M. and M.B. Rosenwein. (1989). “An Improved Dual Based Algorithm for the Generalized Assignment Problem.” Operations Research 37, 658–663.Google Scholar

  • Higgins, A.J. (2001). “A Dynamic Tabu Search for Large-Scale Generalised Assignment Problems.” Computers and Operations Research 28, 1039–1048.CrossRefMathSciNetGoogle Scholar

  • Laguna, M., J. Kelly, J. Gonzalez-Velarde, and F. Glover. (1995). “Tabu Search for the Multilevel Generalized Assignment Problem.” EuropeanJournal of Operational Research 82, 176–189.CrossRefGoogle Scholar

  • Lorena, L.A.N. and M.G. Narcisco. (1996). “Relaxation Heuristics for a Generalized Assignment Problem.” European Journal of Operational Research 91, 600–610.CrossRefGoogle Scholar

  • Martello, S. and P. Toth. (1990). Knapsack Problems: Algorithms and Computer implementations. Chichester, England: John Wiley and Sons.Google Scholar

  • Nauss, R.M. (2003) “Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach.” INFORMS Journal on Computing 15, 249–266.CrossRefGoogle Scholar

  • Osman, I.H. (1995). “Heuristics for the Generalised Assignment Problem: Simulated Annealing and Tabu Search Approaches.” OR Spektrum 17, 211–225.CrossRefGoogle Scholar

  • Ross, G.T. and R.M. Soland. (1975). “A Branch and Bound Algorithm for the Generalized Assignment Problem.” Mathematical Programming 8, 91–103.CrossRefGoogle Scholar

  • Savelsbergh, M. (1997). “A Branch-and-Price Algorithm for the Generalized Assignment Problem.” Operations Research 45, 831–841.Google Scholar

  • Shmoys, D and E. Tardos. (1993). “An Approximation Algorithm for the Generalized Assignment Problem.” Mathematical Programming 62, 461–474.CrossRefGoogle Scholar

  • Trick, M.A. (1992). “A Linear Relaxation Heuristic for the Generalised Assignment Problem.” Naval Research Logistics 39, 137–151.MathSciNetGoogle Scholar

  • Wilson, J.M. (1997a). “A Genetic Algorithm for the Generalised Assignment Problem.” Journal of the Operational Research Society 48, 804–809.CrossRefGoogle Scholar

  • Wilson, J.M. (1997b). “A Simple Dual Algorithm for the Generalised Assignment Problem. ” Journal of Heuristics 2, 303–311.CrossRefGoogle Scholar

  • Yagiura, M, T Yamaguchi, and T. Ibaraki. (1998). “A Variable Depth Search Algorithm with Branching Search for the Generalized Assignment Problem.” Optimization Methods and Software 10, 419–441.Google Scholar

  • Yagiura, M, T. Ibaraki, and F. Glover. (2002). “A Path Relinking Approach for the Generalized Assignment Problem.” In Proceedings of the International Symposium on Scheduling, Japan, June 4–6, 2002, pp. 105–108.Google Scholar

  • Yagiura, M, T. Ibaraki, and F. Glover. (2004). “An Ejection Chain Approach for the Generalized Assignment Problem.” INFORMS Journal on Computing 16, 133–151.CrossRefMathSciNetGoogle Scholar

  • 0 comments

    Leave a Reply

    Your email address will not be published. Required fields are marked *