×

Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns. (English) Zbl 0896.90136

Summary: We give polynomial time algorithms for a job scheduling problem. By duality, we transform a special 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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: DOI