IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v1y1998i4d10.1023_a1009738610804.html
   My bibliography  Save this article

Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns

Author

Listed:
  • Pu Cai

    (State University of New York at Buffalo)

  • Jin-yi Cai

    (State University of New York at Buffalo)

  • Ashish V. Naik

    (University of Chicago)

Abstract

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

Suggested Citation

  • Pu Cai & Jin-yi Cai & Ashish V. Naik, 1998. "Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns," Journal of Combinatorial Optimization, Springer, vol. 1(4), pages 367-376, December.
    • Handle: RePEc:spr:jcomop:v:1:y:1998:i:4:d:10.1023_a:1009738610804
    DOI: 10.1023/A:1009738610804
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1009738610804
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1009738610804?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Naik, Ashich V. & Baveja, Alok & Batta, Rajan & Caulkins, Jonathan P., 1996. "Scheduling crackdowns on illicit drug markets," European Journal of Operational Research, Elsevier, vol. 88(2), pages 231-250, January.
    2. Baveja, Alok & Batta, Rajan & Caulkins, Jonathan P. & Karwan, Mark H., 1993. "Modeling the response of illicit drug markets to local enforcement," Socio-Economic Planning Sciences, Elsevier, vol. 27(2), pages 73-89, June.
    3. Caulkins, Jonathan P. & Larson, Richard C. & Rich, Thomas F., 1993. "Geography's impact on the success of focused local drug enforcement operations," Socio-Economic Planning Sciences, Elsevier, vol. 27(2), pages 119-130, June.
    4. Jonathan P. Caulkins, 1993. "Local Drug Markets' Response to Focused Police Enforcement," Operations Research, INFORMS, vol. 41(5), pages 848-863, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ritu Arora & Kavita Gupta, 2018. "Branch and bound algorithm for discrete multi- level linear fractional programming problem," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 28(2), pages 5-21.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Baveja, Alok & Caulkins, Jonathan P. & Liu, Wensheng & Batta, Rajan & Karwan, Mark H., 1997. "When haste makes sense: Cracking down on street markets for illicit drugs," Socio-Economic Planning Sciences, Elsevier, vol. 31(4), pages 293-306, December.
    2. Baveja, Alok & Jamil, Mamnoon & Kushary, Debashis, 2004. "A sequential model for cracking down on street markets for illicit drugs," Socio-Economic Planning Sciences, Elsevier, vol. 38(1), pages 7-41, March.
    3. Ginoux, Jean-Marc & Naeck, Roomila & Ruhomally, Yusra Bibi & Dauhoo, Muhammad Zaid & Perc, Matjaž, 2019. "Chaos in a predator–prey-based mathematical model for illicit drug consumption," Applied Mathematics and Computation, Elsevier, vol. 347(C), pages 502-513.
    4. Baveja, A. & Feichtinger, G. & Hartl, R.F. & Haunschmied, J.L. & Kort, P.M., 1999. "A Resource-Constrained Optimal Control Model for Crackdown on Illicit Drug Markets," Discussion Paper 1999-85, Tilburg University, Center for Economic Research.
    5. Gragnani, A. & Rinaldi, S. & Feichtinger, G., 1997. "Dynamics of drug consumption: a theoretical model," Socio-Economic Planning Sciences, Elsevier, vol. 31(2), pages 127-137, June.
    6. Kort, P.M. & Feichtinger, G. & Hartl, R.F. & Haunschmied, J.L., 1996. "Optimal Enforcement Policies (Crackdowns) on a Drug Market," Other publications TiSEM 8f874586-670a-470a-95a6-b, Tilburg University, School of Economics and Management.
    7. Redmond, Michael & Baveja, Alok, 2002. "A data-driven software tool for enabling cooperative information sharing among police departments," European Journal of Operational Research, Elsevier, vol. 141(3), pages 660-678, September.
    8. Chi-Bin Cheng & Hsu-Shih Shih & Boris Chen, 2017. "Subsidy rate decisions for the printer recycling industry by bi-level optimization techniques," Operational Research, Springer, vol. 17(3), pages 901-919, October.
    9. V. Borisov & G. Feichtinger & A. Kryazhimskii, 2000. "Optimal Enforcement on a Pure Seller's Market of Illicit Drugs," Journal of Optimization Theory and Applications, Springer, vol. 106(1), pages 1-22, July.
    10. Wang, Shoou-Jiun & Batta, Rajan & Rump, Christopher M., 2005. "Stability of a crime level equilibrium," Socio-Economic Planning Sciences, Elsevier, vol. 39(3), pages 229-244, September.
    11. Feichtinger, Gustav & Grienauer, Waltraud & Tragler, Gernot, 2002. "Optimal dynamic law enforcement," European Journal of Operational Research, Elsevier, vol. 141(1), pages 58-69, August.
    12. Kaya, C. Yalcin, 2004. "Time-optimal switching control for the US cocaine epidemic," Socio-Economic Planning Sciences, Elsevier, vol. 38(1), pages 57-72, March.
    13. Naik, Ashich V. & Baveja, Alok & Batta, Rajan & Caulkins, Jonathan P., 1996. "Scheduling crackdowns on illicit drug markets," European Journal of Operational Research, Elsevier, vol. 88(2), pages 231-250, January.
    14. Leonardo Raffo López, 2015. "Law enforcement and drug trafficking networks: a simple model," Documentos de Trabajo 13014, Universidad del Valle, CIDSE.
    15. Caulkins, Jonathan P. & Feichtinger, Gustav & Tragler, Gernot & Wallner, Dagmar, 2010. "When in a drug epidemic should the policy objective switch from use reduction to harm reduction?," European Journal of Operational Research, Elsevier, vol. 201(1), pages 308-318, February.
    16. Stolzenberg, Lisa & D'Alessio, Stewart J., 2003. "A multilevel analysis of the effect of cocaine price on cocaine use among arrestees," Journal of Criminal Justice, Elsevier, vol. 31(2), pages 185-195.
    17. Daniel Mejía, 2008. "The War on Illegal Drugs in Producer and Consumer Countries: A Simple Analytical Framework," CESifo Working Paper Series 2459, CESifo.
    18. Anthony A. Braga, 2001. "The Effects of Hot Spots Policing on Crime," The ANNALS of the American Academy of Political and Social Science, , vol. 578(1), pages 104-125, November.
    19. Burke, Patrick J., 2022. "Examining drug enforcement by specialized police units in Chicago, 2009-2019," Journal of Criminal Justice, Elsevier, vol. 81(C).
    20. Bertsimas, Dimitris. & Niño-Mora, Jose., 1994. "Restless bandit, linear programming relaxations and a primal-dual heuristic," Working papers 3727-94., Massachusetts Institute of Technology (MIT), Sloan School of Management.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:1:y:1998:i:4:d:10.1023_a:1009738610804. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.