Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns

摘要

We give polynomial time algorithms for a job scheduling problem. By duality we transform a special case of the drug market crackdown scheduling problem to the above job scheduling problem and thus derive polynomial time algorithms to the second problem. Finally, using the algorithm for the special case, we develop a quasipolynomial time approximation algorithm for the general case of the drug market crackdown scheduling problem with monomial cost functions.