• DocumentCode
    1868987
  • Title

    An Improved Preprocessing Algorithm for the Rational Objective Function Problem with Fixed Scale Subset

  • Author

    Yin, Ying ; Zhang, Tongquan

  • Author_Institution
    Dept. of Math., Kunming Univ. of Sci. & Technol., Kunming, China
  • fYear
    2010
  • fDate
    10-12 Dec. 2010
  • Firstpage
    1
  • Lastpage
    4
  • Abstract
    Motivated by the results of rational objective functions on spanning tree, assignment and cycle cover problems, etc. We consider rational objective functions with fixed scale subset problems which includes spanning tree, assignment and cycle cover problems. We design a preprocessing algorithm for it, and prove that our algorithm improves the result of N. Megiddo and the result of M. Shigeno, Y. Saruwatari, T. Matsui on computing complexities, respectively.
  • Keywords
    set theory; trees (mathematics); assignment cover problems; cycle cover problems; fixed scale subset; rational objective function problem; spanning tree; Algorithm design and analysis; Complexity theory; Equations; Graph theory; Operations research; Optimization;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Intelligence and Software Engineering (CiSE), 2010 International Conference on
  • Conference_Location
    Wuhan
  • Print_ISBN
    978-1-4244-5391-7
  • Electronic_ISBN
    978-1-4244-5392-4
  • Type

    conf

  • DOI
    10.1109/CISE.2010.5676721
  • Filename
    5676721
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1868987