Minimum cost spanning extension problems

The proportional rule and the decentralized rule

V. Feltkamp, S.H. Tijs, S. Muto

Research output: Working paperDiscussion paperOther research output

263 Downloads (Pure)

Abstract

Minimum cost spanning extension problems are generalizations of minimum cost spanning tree problems (see Bird 1976) where an existing network has to be extended to connect users to a source. In this paper, we present two cost allocation rules for these problems, viz. the proportional rule and the decentralized rule. We introduce algorithms that generate these rules and prove that both rules are refinements of the irreducible core, as defined in Feltkamp, Tijs and Muto (1994b). We then proceed to axiomatically characterize the proportional rule.
Original languageEnglish
PublisherUnknown Publisher
Number of pages17
Volume1994-96
Publication statusPublished - 1994

Publication series

NameCentER Discussion Paper
Volume1994-96

Fingerprint

Costs
Birds

Keywords

  • Networks
  • Cost Allocation
  • costs and cost price

Cite this

Feltkamp, V., Tijs, S. H., & Muto, S. (1994). Minimum cost spanning extension problems: The proportional rule and the decentralized rule. (CentER Discussion Paper; Vol. 1994-96). Unknown Publisher.
Feltkamp, V. ; Tijs, S.H. ; Muto, S. / Minimum cost spanning extension problems : The proportional rule and the decentralized rule. Unknown Publisher, 1994. (CentER Discussion Paper).
@techreport{2c6cd46b7e724262a4793a5386c90548,
title = "Minimum cost spanning extension problems: The proportional rule and the decentralized rule",
abstract = "Minimum cost spanning extension problems are generalizations of minimum cost spanning tree problems (see Bird 1976) where an existing network has to be extended to connect users to a source. In this paper, we present two cost allocation rules for these problems, viz. the proportional rule and the decentralized rule. We introduce algorithms that generate these rules and prove that both rules are refinements of the irreducible core, as defined in Feltkamp, Tijs and Muto (1994b). We then proceed to axiomatically characterize the proportional rule.",
keywords = "Networks, Cost Allocation, costs and cost price",
author = "V. Feltkamp and S.H. Tijs and S. Muto",
note = "Pagination: 17",
year = "1994",
language = "English",
volume = "1994-96",
series = "CentER Discussion Paper",
publisher = "Unknown Publisher",
type = "WorkingPaper",
institution = "Unknown Publisher",

}

Feltkamp, V, Tijs, SH & Muto, S 1994 'Minimum cost spanning extension problems: The proportional rule and the decentralized rule' CentER Discussion Paper, vol. 1994-96, Unknown Publisher.

Minimum cost spanning extension problems : The proportional rule and the decentralized rule. / Feltkamp, V.; Tijs, S.H.; Muto, S.

Unknown Publisher, 1994. (CentER Discussion Paper; Vol. 1994-96).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Minimum cost spanning extension problems

T2 - The proportional rule and the decentralized rule

AU - Feltkamp, V.

AU - Tijs, S.H.

AU - Muto, S.

N1 - Pagination: 17

PY - 1994

Y1 - 1994

N2 - Minimum cost spanning extension problems are generalizations of minimum cost spanning tree problems (see Bird 1976) where an existing network has to be extended to connect users to a source. In this paper, we present two cost allocation rules for these problems, viz. the proportional rule and the decentralized rule. We introduce algorithms that generate these rules and prove that both rules are refinements of the irreducible core, as defined in Feltkamp, Tijs and Muto (1994b). We then proceed to axiomatically characterize the proportional rule.

AB - Minimum cost spanning extension problems are generalizations of minimum cost spanning tree problems (see Bird 1976) where an existing network has to be extended to connect users to a source. In this paper, we present two cost allocation rules for these problems, viz. the proportional rule and the decentralized rule. We introduce algorithms that generate these rules and prove that both rules are refinements of the irreducible core, as defined in Feltkamp, Tijs and Muto (1994b). We then proceed to axiomatically characterize the proportional rule.

KW - Networks

KW - Cost Allocation

KW - costs and cost price

M3 - Discussion paper

VL - 1994-96

T3 - CentER Discussion Paper

BT - Minimum cost spanning extension problems

PB - Unknown Publisher

ER -

Feltkamp V, Tijs SH, Muto S. Minimum cost spanning extension problems: The proportional rule and the decentralized rule. Unknown Publisher. 1994. (CentER Discussion Paper).