MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

A variant of multi-task n-vehicle exploration problem: Maximizing every processors average profit

Yangyang Xu Jin-chuan Cui

Numerical Linear Algebra mathscidoc:1912.43155

Acta Mathematicae Applicatae Sinica, English Series, 28, (3), 463-474, 2012.7
We discuss a variant of the multi-task <i>n</i>-vehicle exploration problem. Instead of requiring an optimal permutation of vehicles in every group, the new problem requires all vehicles in a group to arrive at the same destination. Given <i>n</i> tasks with assigned consume-time and profit, it may also be viewed as a maximization of every processors average profit. Further, we propose a new kind of partition problem in fractional form and analyze its computational complexity. By regarding fractional partition as a special case, we prove that the average profit maximization problem is NP-hard when the number of processors is fixed and it is strongly NPhard in general. At last, a pseudo-polynomial time algorithm for the average profit maximization problem and the fractional partition problem is presented, using the idea of the pseudo-polynomial time algorithm for the classical partition problem.
No keywords uploaded!
[ Download ] [ 2019-12-21 11:26:18 uploaded by Yangyang_Xu ] [ 555 downloads ] [ 0 comments ] 
@inproceedings{yangyang2012a,
  title={A variant of multi-task n-vehicle exploration problem: Maximizing every processors average profit},
  author={Yangyang Xu, and Jin-chuan Cui},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221112618892135715},
  booktitle={Acta Mathematicae Applicatae Sinica, English Series},
  volume={28},
  number={3},
  pages={463-474},
  year={2012},
}
Yangyang Xu, and Jin-chuan Cui. A variant of multi-task n-vehicle exploration problem: Maximizing every processors average profit. 2012. Vol. 28. In Acta Mathematicae Applicatae Sinica, English Series. pp.463-474. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221112618892135715.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved