Aproximação e compartilhamento de custos em projeto de redes / Approximation and cost-sharing in network design

AUTOR(ES)

Andre Luis Vignatti

DATA DE PUBLICAÇÃO

2006

RESUMO

We consider the interplay of two areas: combinatorial optimization and cost-sharing in network design problems. In the first, we are interested to find a solution with small cost. In the second we would like to share the solution cost between its users. We present algorithms for the problems Connected Facility Location and Rent-or-Buy . These two problems are NP-hard, since they have as a particular case the minimum Steiner tree problem, which is a known NP-hard problem. In the first part of this work, we have the following question as motivation: how to design a good network, i.e., one that satisfies all problem requirements and minimize the overall network construction cost ? In this part, approximation algorithms takes action. Once this cost is determinated, in the second part of the work, another question arises: How to distribute this cost among all users that participate in the network in a fair way? In this part, we will use cost-sharing together with approximation algorithms techniques to answer this question.

ASSUNTO(S)

otimização combinatoria computer theory teoria da computação combinatorial optimization algorithms algoritmos - programação linear

Documentos Relacionados

• Cost-sharing and the use of general medical physicians for outpatient mental health care.
• The direct and indirect effects of cost-sharing on the use of preventive services.
• A cost-sharing formula for online circulation and a union catalog through a regional, multitype library cooperative.
• Physician response to the United Mine Workers' cost-sharing program: the other side of the coin.
• The effects of cost-sharing on essential drug prescriptions, utilization of medical care and outcomes after acute myocardial infarction in elderly patients