New techniques for cost sharing in combinatorial optimization games

DOI10.1007/s10107-010-0357-7zbMath1194.91036OpenAlexW2163345326WikidataQ57702201 ScholiaQ57702201MaRDI QIDQ2638367

Adam N. Letchford, Alberto Caprara

Publication date: 16 September 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/45297/1/10.pdf

zbMATH Keywords

cooperative gamesvalid inequalitiescombinatorial optimization gamestraveling salesman gameoptimal cost sharesvehicle routing game

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Cooperative games (91A12) Linear programming (90C05) Combinatorial optimization (90C27) Combinatorial games (91A46) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games, Stochastic linear programming games with concave preferences, Finding the nucleoli of large cooperative games, Carrier collaboration with the simultaneous presence of transferable and non-transferable utilities, Using \(\ell^p\)-norms for fairness in combinatorial optimisation, Allocating costs in set covering problems, Computing Near-Optimal Stable Cost Allocations for Cooperative Games by Lagrangian Relaxation, Cooperative location games based on the minimum diameter spanning Steiner subgraph problem, A cooperative location game based on the 1-center location problem, A competitive solution for cooperative truckload delivery, A review on cost allocation methods in collaborative transportation, Simultaneous Penalization and Subsidization for Stabilizing Grand Cooperation, OPEN PROBLEMS IN COOPERATIVE LOCATION GAMES

Uses Software

• VRP

Cites Work

• Approximately fair cost allocation in metric traveling salesman games
• On the core of a traveling salesman cost allocation game
• A result on projection for the vehicle routing problem
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• Traveling salesman games
• Geometric algorithms and combinatorial optimization
• On approximately fair cost allocation in Euclidean TSP games
• Multistars, partial multistars and the capacitated vehicle routing problem
• Traveling salesman games with the Monge property
• On the nucleolus of the basic vehicle routing game
• The assignment game. I: The core
• Projection results for vehicle routing
• Traveling the boundary of Minkowski sums.
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• Decomposition Principle for Linear Programs
• Minimum cost spanning tree games
• Odd Minimum Cut-Sets and b-Matchings
• The Circuit Polytope: Facets
• Cooperative facility location games
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• Maximum matching and a polyhedron with 0,1-vertices
• Integer Programming and Combinatorial Optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item