IDEAS home Printed from https://ideas.repec.org/p/mit/sloanp/7407.html
   My bibliography  Save this paper

Approximate Local Search in Combinatorial Optimization

Author

Listed:
  • Orlin, James
  • Punnen, Abraham
  • Schulz, Andreas

Abstract

Local search algorithms for combinational optimization problems are in general of pseudopolynomial running time and polynomial-time algorithms are often not known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of

Suggested Citation

  • Orlin, James & Punnen, Abraham & Schulz, Andreas, 2004. "Approximate Local Search in Combinatorial Optimization," Working papers 4325-03, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    • Handle: RePEc:mit:sloanp:7407
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/1721.1/7407
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Andreas S. Schulz & Robert Weismantel, 2002. "The Complexity of Generic Primal Algorithms for Solving General Integer Programs," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 681-692, November.
    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. Chien, Steve & Sinclair, Alistair, 2011. "Convergence to approximate Nash equilibria in congestion games," Games and Economic Behavior, Elsevier, vol. 71(2), pages 315-327, March.
    2. Cemalettin Öztürk & F. Zeynep Sargut & M. Arslan Örnek & Deniz Türsel Eliiyi, 2017. "Optimisation and heuristic approaches for assigning inbound containers to outbound carriers," Maritime Policy & Management, Taylor & Francis Journals, vol. 44(7), pages 825-836, October.
    3. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    4. Huang, Zhengxin & Zhou, Yuren & Xia, Xiaoyun & Lai, Xinsheng, 2020. "An improved (1+1) evolutionary algorithm for k-median clustering problem with performance guarantee," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    5. Pisut Pongchairerks, 2019. "A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem," Complexity, Hindawi, vol. 2019, pages 1-11, March.
    6. Daya Ram Gaur & Ramesh Krishnamurti & Rajeev Kohli, 2009. "Conflict Resolution in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 57(5), pages 1098-1105, October.
    7. Asaf Levin & Uri Yovel, 2014. "Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees," Journal of Combinatorial Optimization, Springer, vol. 28(4), pages 726-747, November.
    8. T Öncan & S N Kabadi & K P K Nair & A P Punnen, 2008. "VLSN search algorithms for partitioning problems using matching neighbourhoods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(3), pages 388-398, March.
    9. Brad D. Woods & Abraham P. Punnen, 2020. "A class of exponential neighbourhoods for the quadratic travelling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 303-332, August.
    10. Shuyang Sheng, 2020. "A Structural Econometric Analysis of Network Formation Games Through Subnetworks," Econometrica, Econometric Society, vol. 88(5), pages 1829-1858, September.
    11. Alekseeva, Ekaterina & Kochetov, Yuri & Plyasunov, Alexander, 2008. "Complexity of local search for the p-median problem," European Journal of Operational Research, Elsevier, vol. 191(3), pages 736-752, December.
    12. Martin Gairing & Rahul Savani, 2019. "Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 1101-1121, August.
    13. Gallego, Camilo A., 2022. "Intertemporal effects of imperfect competition through forward contracts in wholesale electricity markets," Energy Economics, Elsevier, vol. 107(C).
    14. Brad D. Woods & Abraham P. Punnen, 0. "A class of exponential neighbourhoods for the quadratic travelling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-30.

    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.

      More about this item

      Statistics

      Access and download statistics

      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:mit:sloanp:7407. 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: None (email available below). General contact details of provider: https://edirc.repec.org/data/ssmitus.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.