Single node service provision with fixed charges

S. Dye, L. Stougie, A. Tomasgard

Research output: Book/ReportReportAcademic

28 Downloads (Pure)

Abstract

The service provision problem described in this paper comes from an application of distributed processing in telecommunication networks. The objective is to maximize a service provider's profit from offering computational based services to customers. The services are built from software applications called subservices. The service provider has limited capacity of some resources and therefore must choose from a set of software subservices those he would like to offer. He maximizes profit which depends both on the number of requests met and fixed charges for installing the subservices. A fixed charge is positive when it is charged by the service provider and negative if it is an amount the service provider must pay for example to license the subservice. Our main interest in this problem comes from it being a subproblem in a scenario decomposition of the service provision problem with stochastic demand. We assume stochasticity is represented in terms of scenarios from a discrete probability distribution. The fixed charges can be interpreted as dual prices on the linking constraints in a variable split that makes the stochastic problem separable in its demand scenarios. The main contribution of the paper is to give a pseudo-polynomial time algorithm to solve the fixed charge problem and describe how this algorithm can be used in a fully polynomial time approximation scheme. It is also indicated how the results from this paper are used in a decomposition scheme for the stochastic service provision problem.
Original languageEnglish
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Number of pages29
Publication statusPublished - 1999

Publication series

NameMemorandum COSOR
Volume9904
ISSN (Print)0926-4493

Fingerprint

Service provision
Node
Service provider
Fixed charge
Scenarios
Decomposition
Software
Profit
Polynomials
Probability distribution
Polynomial-time algorithm
Stochastic demand
Approximation
License
Telecommunication network
Resources

Cite this

Dye, S., Stougie, L., & Tomasgard, A. (1999). Single node service provision with fixed charges. (Memorandum COSOR; Vol. 9904). Eindhoven: Technische Universiteit Eindhoven.
Dye, S. ; Stougie, L. ; Tomasgard, A. / Single node service provision with fixed charges. Eindhoven : Technische Universiteit Eindhoven, 1999. 29 p. (Memorandum COSOR).
@book{e6ce8676b771410eb7a4cb212144f39c,
title = "Single node service provision with fixed charges",
abstract = "The service provision problem described in this paper comes from an application of distributed processing in telecommunication networks. The objective is to maximize a service provider's profit from offering computational based services to customers. The services are built from software applications called subservices. The service provider has limited capacity of some resources and therefore must choose from a set of software subservices those he would like to offer. He maximizes profit which depends both on the number of requests met and fixed charges for installing the subservices. A fixed charge is positive when it is charged by the service provider and negative if it is an amount the service provider must pay for example to license the subservice. Our main interest in this problem comes from it being a subproblem in a scenario decomposition of the service provision problem with stochastic demand. We assume stochasticity is represented in terms of scenarios from a discrete probability distribution. The fixed charges can be interpreted as dual prices on the linking constraints in a variable split that makes the stochastic problem separable in its demand scenarios. The main contribution of the paper is to give a pseudo-polynomial time algorithm to solve the fixed charge problem and describe how this algorithm can be used in a fully polynomial time approximation scheme. It is also indicated how the results from this paper are used in a decomposition scheme for the stochastic service provision problem.",
author = "S. Dye and L. Stougie and A. Tomasgard",
year = "1999",
language = "English",
series = "Memorandum COSOR",
publisher = "Technische Universiteit Eindhoven",

}

Dye, S, Stougie, L & Tomasgard, A 1999, Single node service provision with fixed charges. Memorandum COSOR, vol. 9904, Technische Universiteit Eindhoven, Eindhoven.

Single node service provision with fixed charges. / Dye, S.; Stougie, L.; Tomasgard, A.

Eindhoven : Technische Universiteit Eindhoven, 1999. 29 p. (Memorandum COSOR; Vol. 9904).

Research output: Book/ReportReportAcademic

TY - BOOK

T1 - Single node service provision with fixed charges

AU - Dye, S.

AU - Stougie, L.

AU - Tomasgard, A.

PY - 1999

Y1 - 1999

N2 - The service provision problem described in this paper comes from an application of distributed processing in telecommunication networks. The objective is to maximize a service provider's profit from offering computational based services to customers. The services are built from software applications called subservices. The service provider has limited capacity of some resources and therefore must choose from a set of software subservices those he would like to offer. He maximizes profit which depends both on the number of requests met and fixed charges for installing the subservices. A fixed charge is positive when it is charged by the service provider and negative if it is an amount the service provider must pay for example to license the subservice. Our main interest in this problem comes from it being a subproblem in a scenario decomposition of the service provision problem with stochastic demand. We assume stochasticity is represented in terms of scenarios from a discrete probability distribution. The fixed charges can be interpreted as dual prices on the linking constraints in a variable split that makes the stochastic problem separable in its demand scenarios. The main contribution of the paper is to give a pseudo-polynomial time algorithm to solve the fixed charge problem and describe how this algorithm can be used in a fully polynomial time approximation scheme. It is also indicated how the results from this paper are used in a decomposition scheme for the stochastic service provision problem.

AB - The service provision problem described in this paper comes from an application of distributed processing in telecommunication networks. The objective is to maximize a service provider's profit from offering computational based services to customers. The services are built from software applications called subservices. The service provider has limited capacity of some resources and therefore must choose from a set of software subservices those he would like to offer. He maximizes profit which depends both on the number of requests met and fixed charges for installing the subservices. A fixed charge is positive when it is charged by the service provider and negative if it is an amount the service provider must pay for example to license the subservice. Our main interest in this problem comes from it being a subproblem in a scenario decomposition of the service provision problem with stochastic demand. We assume stochasticity is represented in terms of scenarios from a discrete probability distribution. The fixed charges can be interpreted as dual prices on the linking constraints in a variable split that makes the stochastic problem separable in its demand scenarios. The main contribution of the paper is to give a pseudo-polynomial time algorithm to solve the fixed charge problem and describe how this algorithm can be used in a fully polynomial time approximation scheme. It is also indicated how the results from this paper are used in a decomposition scheme for the stochastic service provision problem.

M3 - Report

T3 - Memorandum COSOR

BT - Single node service provision with fixed charges

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -

Dye S, Stougie L, Tomasgard A. Single node service provision with fixed charges. Eindhoven: Technische Universiteit Eindhoven, 1999. 29 p. (Memorandum COSOR).