On capital investment

We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new machine and a resulting productivity gain, i.e., a lower production cost for one unit of product. The g...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Azar, Y., Bartal, Y., Feuerstein, E., Fiat, A., Leonardi, S., Rosén, A.
Formato:	JOUR
Materias:	Competitive ratio On-line algorithms On-line financial problems
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_01784617_v25_n1_p22_Azar
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_01784617_v25_n1_p22_Azar
record_format	dspace
spelling	todo:paper_01784617_v25_n1_p22_Azar2023-10-03T15:08:17Z On capital investment Azar, Y. Bartal, Y. Feuerstein, E. Fiat, A. Leonardi, S. Rosén, A. Competitive ratio On-line algorithms On-line financial problems We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new machine and a resulting productivity gain, i.e., a lower production cost for one unit of product. The goal is that of minimizing the total production costs and capital costs when future demand for the product being produced and investment opportunities are unknown. This can be viewed as a generalization of the ski-rental problem and related to the mortgage problem [3]. If all possible capital investments obey the rule that lower production costs require higher capital investments, then we present an algorithm with constant competitive ratio. If new opportunities may be strictly superior to previous ones (in terms of both capital cost and production cost), then we give an algorithm which is O(min{1 + log C, 1 + log log P, 1 + log M}) competitive, where C is the ratio between the highest and the lowest capital costs, P is the ratio between the highest and the lowest production costs, and M is the number of investment opportunities. We also present a lower bound on the competitive ratio of any on-line algorithm for this case, which is Ω (min{log C, log log P/ log log log P, log M/ log log M}). This shows that the competitive ratio of our algorithm is tight (up to constant factors) as a function of C, and not far from the best achievable as a function of P and M. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_01784617_v25_n1_p22_Azar
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Competitive ratio On-line algorithms On-line financial problems
spellingShingle	Competitive ratio On-line algorithms On-line financial problems Azar, Y. Bartal, Y. Feuerstein, E. Fiat, A. Leonardi, S. Rosén, A. On capital investment
topic_facet	Competitive ratio On-line algorithms On-line financial problems
description	We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new machine and a resulting productivity gain, i.e., a lower production cost for one unit of product. The goal is that of minimizing the total production costs and capital costs when future demand for the product being produced and investment opportunities are unknown. This can be viewed as a generalization of the ski-rental problem and related to the mortgage problem [3]. If all possible capital investments obey the rule that lower production costs require higher capital investments, then we present an algorithm with constant competitive ratio. If new opportunities may be strictly superior to previous ones (in terms of both capital cost and production cost), then we give an algorithm which is O(min{1 + log C, 1 + log log P, 1 + log M}) competitive, where C is the ratio between the highest and the lowest capital costs, P is the ratio between the highest and the lowest production costs, and M is the number of investment opportunities. We also present a lower bound on the competitive ratio of any on-line algorithm for this case, which is Ω (min{log C, log log P/ log log log P, log M/ log log M}). This shows that the competitive ratio of our algorithm is tight (up to constant factors) as a function of C, and not far from the best achievable as a function of P and M.
format	JOUR
author	Azar, Y. Bartal, Y. Feuerstein, E. Fiat, A. Leonardi, S. Rosén, A.
author_facet	Azar, Y. Bartal, Y. Feuerstein, E. Fiat, A. Leonardi, S. Rosén, A.
author_sort	Azar, Y.
title	On capital investment
title_short	On capital investment
title_full	On capital investment
title_fullStr	On capital investment
title_full_unstemmed	On capital investment
title_sort	on capital investment
url	http://hdl.handle.net/20.500.12110/paper_01784617_v25_n1_p22_Azar
work_keys_str_mv	AT azary oncapitalinvestment AT bartaly oncapitalinvestment AT feuersteine oncapitalinvestment AT fiata oncapitalinvestment AT leonardis oncapitalinvestment AT rosena oncapitalinvestment
_version_	1807318678788636672

On capital investment

Ejemplares similares