• DocumentCode
    2146714
  • Title

    The prize-collecting call control problem

  • Author

    Weidong Li ; Shi, Yaomin ; Guan, Li ; Li, Weidong

  • Author_Institution
    School of Resource Environment and Earth Sciences, Yunnan University, Kunming, China
  • fYear
    2010
  • fDate
    4-6 Dec. 2010
  • Firstpage
    1609
  • Lastpage
    1612
  • Abstract
    The prize-collecting call control problem is to minimize the sum of the maximum load on the edges and the total penalty costs of the rejected calls. In this paper, we design a 2-approximation algorithm using linear programming rounding technique, and a 1.58-approximation algorithm using randomized rounding technique for this problem. We also present some optimal algorithms and approximation algorithms for some special graphs including rings, lines and stars.
  • Keywords
    Algorithm design and analysis; Approximation algorithms; Approximation methods; Optimized production technology; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Information Science and Engineering (ICISE), 2010 2nd International Conference on
  • Conference_Location
    Hangzhou, China
  • Print_ISBN
    978-1-4244-7616-9
  • Type

    conf

  • DOI
    10.1109/ICISE.2010.5691199
  • Filename
    5691199
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2146714