Further Study on Reverse 1-Center Problem on Trees
| Autor: | Ali Reza Sepasian, Javad Tayyebi |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
021103 operations research
Mathematical analysis 0211 other engineering and technologies Ocean Engineering 0102 computer and information sciences 02 engineering and technology Function (mathematics) Management Science and Operations Research Edge (geometry) Type (model theory) 01 natural sciences 010201 computation theory & mathematics Center (algebra and category theory) Value (mathematics) Mathematics |
| Zdroj: | Asia-Pacific Journal of Operational Research. 37:2050034 |
| ISSN: | 1793-7019 0217-5959 |
| DOI: | 10.1142/s0217595920500347 |
| Popis: | This paper studies two types of reverse 1-center problems under uniform linear cost function where edge lengths are allowed to reduce. In the first type, the aim is that the objective value is bounded by a prescribed fixed value [Formula: see text] at minimum cost. The aim of the other is to improve the objective value as much as possible within a given budget. An algorithm based on dynamic programming is proposed to solve the first problem in linear time. Then, this algorithm is applied as a subroutine to design an algorithm to solve the second type of the problem in [Formula: see text] time in which [Formula: see text] is a fixed number dependent on the problem parameters. Under the similarity assumption, this algorithm has a better complexity than the Nguyen algorithm (2013) with quadratic-time complexity. Some numerical experiments are conducted to validate this fact in practice. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|