The k-centrum Chinese postman delivery problem and a related cost allocation game

DOI10.1016/J.DAM.2014.07.021MaRDI QIDQ477339zbMATH OpenOpenAlexFDO

Authors Daniel Granot, Frieda Granot, Harshavardhan Ravichandran

Publication date 3 December 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2014.07.021

zbMATH Keywords

Chinese postman problemcore\(k\)-centrum Chinese postman problemChinese postman gamesubmodular game

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Cooperative games (91A12) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Recommendations

• On games arising from multi-depot Chinese postman problems
• Cost allocation in the Chinese postman problem
• A Note on K-Best Solutions to the Chinese Postman Problem
• The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases
• An approximation algorithm for solving the heterogeneous Chinese postman problem
• An optimal algorithm for the mixed Chinese postman problem
• Approximation algorithms for solving the heterogeneous Chinese postman problem
• scientific article; zbMATH DE number 4211828
• Approximate solutions for the maximum benefit chinese postman problem
• Structural parameterizations of the mixed Chinese postman problem

Cites work

• A fundamental problem in vehicle routing
• Algorithms for two bottleneck optimization problems
• Cores of convex games
• Cost allocation in the Chinese postman problem
• Minimizing the sum of the \(k\) largest functions in linear time.
• Minimum cost spanning tree games
• On Chinese postman games where residents of each road pay the cost of their road
• On \(k\)-sum optimization
• On cost allocation for a spanning tree: A game theoretic approach
• On graphs which can or cannot induce Chinese Postman games with a non-empty core
• On some balanced, totally balanced and submodular delivery games
• On the concavity of delivery games
• On the core of linear production games
• On the equivalence between some local and global Chinese postman and traveling salesman graphs
• The \(k\)-centrum multi-facility location problem
• The bottleneck transportation problem

Cited in

(4)

• Revisiting \(k\)-sum optimization
• On games arising from multi-depot Chinese postman problems
• An updated annotated bibliography on arc routing problems
• Security routing games with multivehicle Chinese postman problem

This page was built for publication: The \(k\)-centrum Chinese postman delivery problem and a related cost allocation game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477339)