Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems

Hongtan Sun () and Thomas C. Sharkey ()
Additional contact information
Hongtan Sun: Rensselaer Polytechnic Institute
Thomas C. Sharkey: Rensselaer Polytechnic Institute

Journal of Global Optimization, 2017, vol. 68, issue 3, No 7, 623-640

Abstract: Abstract In this paper, we provide approximation guarantees of algorithms for the fractional optimization problems arising in the dispatching rules from recent literature for Integrated Network Design and Scheduling problems. These fractional optimization problem are proved to be NP-hard. The approximation guarantees are based both on the number of arcs in the network and on the number of machines in the scheduling environment. We further demonstrate, by example, the tightness of the factors for these approximation algorithms.

Keywords: Approximation algorithm; Fractional optimization; Integrated Network Design and Scheduling; Complexity analysis (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0498-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:68:y:2017:i:3:d:10.1007_s10898-017-0498-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0498-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().