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
ACESSO AO ARTIGO
http://libdigi.unicamp.br/document/?code=vtls000416358Documentos 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