IDEAS home Printed from https://ideas.repec.org/a/inm/orinte/v32y2002i3p30-61.html
   My bibliography  Save this article

Tutorial on Computational Complexity

Author

Listed:
  • Craig A. Tovey

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

Computational complexity measures how much work is required to solve different problems. It provides a useful classification tool for OR/MS practitioners, especially when tackling discrete deterministic problems. Use it to tell, in advance, whether a problem is easy or hard. Knowing this won't solve your problem, but it will help you to decide what kind of solution method is appropriate. Complexity analysis helps you to understand and deal with hard problems. It can pinpoint the nasty parts of your problem, alert you to a special structure you can take advantage of, and guide you to model more effectively. You will solve your problem better when you know the borders between hard and easy. Locating the difficulty can indicate where to aggregate, decompose, or simplify. To detect and prove computational difficulty, show that a known hard problem from the literature is embedded within your problem. Fix parameters of your problem to arrive at the known hard problem, or use specialization, padding, forcing, or the more difficult gadget proofs. Study contrasting pairs of easy and hard problems to develop your intuitive ability to assess complexity.

Suggested Citation

  • Craig A. Tovey, 2002. "Tutorial on Computational Complexity," Interfaces, INFORMS, vol. 32(3), pages 30-61, June.
    • Handle: RePEc:inm:orinte:v:32:y:2002:i:3:p:30-61
    DOI: 10.1287/inte.32.3.30.39
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/inte.32.3.30.39
    Download Restriction: no
    File URL: https://libkey.io/10.1287/inte.32.3.30.39?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
    ---><---

    References listed on IDEAS

    as
    1. Arthur M. Geoffrion, 1987. "An Introduction to Structured Modeling," Management Science, INFORMS, vol. 33(5), pages 547-588, May.
    2. Michael W. Carter & Craig A. Tovey, 1992. "When Is the Classroom Assignment Problem Hard?," Operations Research, INFORMS, vol. 40(1-supplem), pages 28-39, February.
    3. Julien Bramel & David Simchi-Levi, 1995. "A Location Based Heuristic for General Routing Problems," Operations Research, INFORMS, vol. 43(4), pages 649-660, August.
    4. Steven T. Hackman & Robert C. Leachman, 1989. "A General Framework for Modeling Production," Management Science, INFORMS, vol. 35(4), pages 478-495, April.
    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. Alexandra M. Newman & Martin Weiss, 2013. "A Survey of Linear and Mixed-Integer Optimization Tutorials," INFORMS Transactions on Education, INFORMS, vol. 14(1), pages 26-38, September.
    2. Mavrommatis, George, 2008. "Learning objects and objectives towards automatic learning construction," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1449-1458, June.
    3. Yang, Yongjie & Dimitrov, Dinko, 2023. "Group control for consent rules with consecutive qualifications," Mathematical Social Sciences, Elsevier, vol. 121(C), pages 1-7.
    4. Constantine N. Goulimis, 2007. "ASP, The Art and Science of Practice: Appeal to NP-Completeness Considered Harmful: Does the Fact That a Problem Is NP-Complete Tell Us Anything?," Interfaces, INFORMS, vol. 37(6), pages 584-586, December.
    5. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    6. Yongjie Yang & Dinko Dimitrov, 2019. "The complexity of shelflisting," Theory and Decision, Springer, vol. 86(1), pages 123-141, February.
    7. Milad Zamanifar & Timo Hartmann, 2020. "Optimization-based decision-making models for disaster recovery and reconstruction planning of transportation networks," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 104(1), pages 1-25, October.

    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. Ciamac C. Moallemi & Utkarsh Patange, 2024. "Hybrid Scheduling with Mixed-Integer Programming at Columbia Business School," Interfaces, INFORMS, vol. 54(3), pages 222-240, May.
    2. Gu, Jifa & Tang, Xijin, 2005. "Meta-synthesis approach to complex system modeling," European Journal of Operational Research, Elsevier, vol. 166(3), pages 597-614, November.
    3. Cherchye, Laurens & De Rock, Bram & Kerstens, Pieter Jan, 2018. "Production with storable and durable inputs: Nonparametric analysis of intertemporal efficiency," European Journal of Operational Research, Elsevier, vol. 270(2), pages 498-513.
    4. Kefeli, Ali & Uzsoy, Reha & Fathi, Yahya & Kay, Michael, 2011. "Using a mathematical programming model to examine the marginal price of capacitated resources," International Journal of Production Economics, Elsevier, vol. 131(1), pages 383-391, May.
    5. Park, Hyeongjun & Park, Dongjoo & Jeong, In-Jae, 2016. "An effects analysis of logistics collaboration in last-mile networks for CEP delivery services," Transport Policy, Elsevier, vol. 50(C), pages 115-125.
    6. César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    7. Dolk, Daniel R., 2000. "Integrated model management in the data warehouse era," European Journal of Operational Research, Elsevier, vol. 122(2), pages 199-218, April.
    8. Jeffrey Kingston, 2012. "Resource assignment in high school timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 241-254, April.
    9. Phillip O. Kriett & Sebastian Eirich & Martin Grunow, 2017. "Cycle time-oriented mid-term production planning for semiconductor wafer fabrication," International Journal of Production Research, Taylor & Francis Journals, vol. 55(16), pages 4662-4679, August.
    10. Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
    11. C Beyrouthy & E K Burke & D Landa-Silva & B McCollum & P McMullan & A J Parkes, 2009. "Towards improving the utilization of university teaching space," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 130-143, January.
    12. Makowski, Marek, 2005. "A structured modeling technology," European Journal of Operational Research, Elsevier, vol. 166(3), pages 615-648, November.
    13. Pecchioli, Bruno & Moroz, David, 2023. "Do geographical appellations provide useful quality signals? The case of Scotch single malt whiskies," Economic Modelling, Elsevier, vol. 124(C).
    14. Clarence H. Martin, 2004. "Ohio University's College of Business Uses Integer Programming to Schedule Classes," Interfaces, INFORMS, vol. 34(6), pages 460-465, December.
    15. Raa, Birger & Aghezzaf, El-Houssaine, 2009. "A practical solution approach for the cyclic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 192(2), pages 429-441, January.
    16. Ouyang, Yanfeng, 2007. "Design of vehicle routing zones for large-scale distribution systems," Transportation Research Part B: Methodological, Elsevier, vol. 41(10), pages 1079-1093, December.
    17. Chatterjee A K & Mukherjee, Saral, 2006. "Unified Concept of Bottleneck," IIMA Working Papers WP2006-05-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    18. Zhao, Qiu-Hong & Chen, Shuang & Zang, Cun-Xun, 2008. "Model and algorithm for inventory/routing decision in a three-echelon logistics system," European Journal of Operational Research, Elsevier, vol. 191(3), pages 623-635, December.
    19. Oliver Czibula & Hanyu Gu & Aaron Russell & Yakov Zinder, 2017. "A multi-stage IP-based heuristic for class timetabling and trainer rostering," Annals of Operations Research, Springer, vol. 252(2), pages 305-333, May.
    20. Gelman, Irit Askira, 2005. "Addressing time-scale differences among decision-makers through model abstractions," European Journal of Operational Research, Elsevier, vol. 160(2), pages 325-335, January.

    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:inm:orinte:v:32:y:2002:i:3:p:30-61. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.