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
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;
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
DOI :
10.1109/CISE.2010.5676721
