Computing Near-Optimal Stable Cost Allocations for Cooperative Games by Lagrangian Relaxation

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, NJ).Google Scholar
• Aydinliyim T, Vairaktarakis GL (2010) Coordination of outsourced operations to minimize weighted flow time and capacity booking costs. Manufacturing Service Oper. Management 12(2):236–255.Link, Google Scholar
• Bachrach Y, Elkind E, Meir R, Pasechnik D, Zuckerman M, Rothe J, Rosenschein JS (2009) The cost of stability in coalitional games. Mavronicolas M, Papadopoulou VG, eds. Internat. Sympos. Algorithmic Game Theory SAGT 2009, Lecture Notes in Computer Science, Vol. 5814 (Springer, Berlin),122–134.Crossref, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Beresnev V, Kochetov Y, Pashchenko M, Kononov A, Goncharov E, Plyasunov A, Kochetova N, Alekseeva E, Ivanenko D (2006) Benchmark. Accessed June 24, 2016, http://www.math.nsc.ru/AP/benchmarks/english.html.Google Scholar
• Bläser M, Ram LS (2008) Approximately fair cost allocation in metric traveling salesman games. Theory Comput. Syst. 43(1):19–37.Crossref, Google Scholar
• Cai X, Vairaktarakis GL (2012) Coordination of outsourced operations at a third-party facility subject to booking, overtime, and tardiness costs. Oper. Res. 60(6):1436–1450.Link, Google Scholar
• Caprara A, Letchford AN (2010) New techniques for cost sharing in combinatorial optimization games. Math. Programming 124(1–2):93–118.Crossref, Google Scholar
• Chen X (2009) Inventory centralization games with price-dependent demand and quantity discount. Oper. Res. 57(6):1394–1406.Link, Google Scholar
• Chen X, Zhang J (2009) A stochastic programming duality approach to inventory centralization games. Oper. Res. 57(4):840–851.Link, Google Scholar
• Deng X, Ibaraki T, Nagamochi H (1999) Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24(3):751–766.Link, Google Scholar
• Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. Guy R, ed. Combinatorial Structures & Their Applications (Gordon and Breach, New York), 69–87.Google Scholar
• Engevall S, Göthe-Lundgren M, Värbrand P (2004) The heterogeneous vehicle-routing game. Transportation Sci. 38(1):71–85.Link, Google Scholar
• Faigle U, Kern W (1993) On some approximately balanced combinatorial cooperative games. Zeitschrift für Oper. Res. 38(2):141–152.Google Scholar
• Faigle U, Kern W, Paulusma D (2000) Note on the computational complexity of least core concepts for min-cost spanning tree games. Math. Methods Oper. Res. 52(1):23–38.Crossref, Google Scholar
• Faigle U, Fekete SP, Hochstättler W, Kern W (1998) On approximately fair cost allocation in Euclidean TSP games. OR Spectrum 20(1):29–37.Crossref, Google Scholar
• Geoffrion A (1974) Lagrangian relaxation and its uses in integer programming. Math. Programming Stud. 2:82–114.Crossref, Google Scholar
• Goemans MX, Skutella M (2000) Cooperative facility location games. J. Algorithms 50(2):76–85.Google Scholar
• Göthe-Lundgren M, Jörnsten K, Värbrand P (1996) On the nucleolus of the basic vehicle routing game. Math. Programming 72(1):83–100.Crossref, Google Scholar
• Granot D, Huberman G (1981) Minimum cost spanning tree games. Math. Programming 21(1):1–18.Crossref, Google Scholar
• Hartman BC, Dror M, Shaked M (2000) Cores of inventory centralization games. Games Econom. Behav. 31(1):26–49.Crossref, Google Scholar
• He S, Zhang J, Zhang S (2012) Polymatroid optimization, submodularity, and joint replenishment games. Oper. Res. 60(1):128–137.Link, Google Scholar
• Jain K, Mahdian M (2007) Cost sharing. Nisan N, Roughgarden T, Tardos E, Vazirani V, eds. Algorithmic Game Theory (Cambridge University Press, New York), 385–410.Crossref, Google Scholar
• Kern W, Paulusma D (2003) Matching games: The least core and the nucleolus. Math. Oper. Res. 28(2):294–308.Link, Google Scholar
• Kolen A (1983) Solving covering problems and the uncapacitated plant location problem on trees. Eur. J. Oper. Res. 12(3):266–278.Crossref, Google Scholar
• Li G, Li Y, Shu J, Xu D (2013) A cross-monotonic cost-sharing scheme for the concave facility location game. J. Global Optim. 56(4):1325–1334.Crossref, Google Scholar
• Liu L (2015) To stabilize grand coalitions in unbalanced cooperative games. Doctoral dissertation, The Hong Kong University of Science and Technology.Crossref, Google Scholar
• Liu Z (2009) Complexity of core allocation for the bin packing game. Oper. Res. Lett. 37(4):225–229.Crossref, Google Scholar
• Mallozzi L (2011) Cooperative games in facility location situations with regional fixed costs. Optim. Lett. 5(1):173–181.Crossref, Google Scholar
• Martínez-de Albéniz FJ, Rafels C, Ybern N (2013) A procedure to compute the nucleolus of the assignment game. Oper. Res. Lett. 41(6):675–678.Crossref, Google Scholar
• Maschler M, Peleg B, Shapley LS (1979) Geometric properties of the kernel, nucleolus, and related solution concepts. Math. Oper. Res. 4(4):303–338.Link, Google Scholar
• Meir R, Rosenschein JS, Malizia E (2011) Subsidies, stability, and restricted cooperation in coalitional games. Proc. 22nd Internat. Joint Conf. Artificial Intelligence, IJCAI’11, Vol. 1 (AAAI Press, Palo Alto, CA), 301–306.Google Scholar
• Owen G (1975) On the core of linear production games. Math. Programming 9(1):358–370.Crossref, Google Scholar
• Potters JA, Curiel IJ, Tijs SH (1992) Traveling salesman games. Math. Programming 53(1–3):199–211.Crossref, Google Scholar
• Puerto J, Tamir A, Perea F (2011) A cooperative location game based on the 1-center location problem. Eur. J. Oper. Res. 214(2):317–330.Crossref, Google Scholar
• Puerto J, Tamir A, Perea F (2012) Cooperative location games based on the minimum diameter spanning Steiner subgraph problem. Discrete Appl. Math. 160(7):970–979.Crossref, Google Scholar
• Schulz AS, Uhan NA (2010) Sharing supermodular costs. Oper. Res. 58(4, Pt. 2):1051–1056.Link, Google Scholar
• Schulz AS, Uhan NA (2013) Approximating the least core value and least core of cooperative games with supermodular costs. Discrete Optim. 10(2):163–180.Crossref, Google Scholar
• Shapley LS (1953) A value for n-person games. Contributions Theory Games 2:307–317.Google Scholar
• Shapley LS (1971) Cores of convex games. Internat. J. Game Theory 1(1):11–26.Crossref, Google Scholar
• Shapley LS, Shubik M (1971) The assignment game I: The core. Internat. J. Game Theory 1(1):111–130.Crossref, Google Scholar
• Tamir A (1989) On the core of a traveling salesman cost allocation game. Oper. Res. Lett. 8(1):31–34.Crossref, Google Scholar
• Xu D, Yang R (2009) A cost-sharing method for an economic lot-sizing game. Oper. Res. Lett. 37(2):107–110.Crossref, Google Scholar
• Zhang J (2009) Cost allocation for joint replenishment models. Oper. Res. 57(1):146–156.Link, Google Scholar