Centrum Wiskunde & Informatica: Analysis of Christofides' heuristic: some paths are more difficult than cycles

<!DOCTYPE html> <html lang="en"> <head> <title> Centrum Wiskunde & Informatica: Analysis of Christofides' heuristic: some paths are more difficult than cycles </title> <meta http-equiv="X-UA-Compatible" content="IE=edge"/> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/> <meta name="viewport" content="width=device-width, initial-scale=1.0"/> <meta name="citation_title" content="Analysis of Christofides' heuristic: some paths are more difficult than cycles"/> <meta name="citation_author" content="Hoogeveen, J.A."/> <meta name="citation_date" content="1991/01/01"/> <meta name="citation_publication_date" content="1991/01/01"/> <meta name="citation_online_date" content="1991/01/01"/> <meta name="citation_journal_title" content="Operations Research Letters"/> <meta name="citation_volume" content="10"/> <meta name="citation_issue" content="5"/> <meta name="citation_issn" content="0167-6377"/> <meta name="citation_firstpage" content="291"/> <meta name="citation_lastpage" content="295"/> <link rel="alternate" type="application/rdf+xml" title="VIVO" href="https://ir.cwi.nl/pub/2347/rdf"/> <link rel="repository" href="https://ir.cwi.nl/"/> <link rel="me" href="https://ir.cwi.nl/pub/2347/"/> <link rel="view" href="https://ir.cwi.nl/pub/2347"/> <link rel="shortcut icon" type="image/x-icon" href="/static/img/favicon.ico"/> <link rel="stylesheet" type="text/css" href="/static/css/bundle-1.css"/> <script type="text/javascript" src="/static/js/bundle-1.js"></script>   </head> <body> <div id="wrap"> <header> <div class="navbar" style="margin-bottom:0"> <div class="navbar-inner"> <div class="container"> <a class="brand" style="padding:10px;width:200px" href="https://ir.cwi.nl/"> <img alt="university website" style="width:100%" src="https://ir.cwi.nl/cwi.png"/> </a> <a class="hidden" href="https://ir.cwi.nl/year">Publications by Year</a> <ul class="nav"> </ul> <ul class="nav pull-right"> <li id="fat-menu" class="dropdown"> <a class="dropdown-toggle" href="https://ir.cwi.nl/login?next=/pub/2347"> <span class="icon-signin"></span> sign in </a> </li> </ul> </div> </div> </div> </header> <div id="breadcrumb" class="row-fluid"> <div class="span12"> <ul class="breadcrumb"> <li> <a href="https://ir.cwi.nl/col/3692">Operations Research Letters</a> <span class="divider">/</span> </li> <li class="active">Article</li> <li class="pull-right"> <div class="input-append search-box" style="margin-top:-5px"> <label for="search-query-box" style="display:none">Search:</label> <input type="text" class="input-large search-input" id="search-query-box" style="width:250px" value="" name="query"/> <a class="btn btn-primary search-button" style="border-bottom:1px solid rgba(0, 0, 0, 0.25)" href="https://ir.cwi.nl/search#"> <span class="icon-search"></span> Search </a> </div> </li> </ul> </div> </div> <div class="row-fluid"> <div id="main-left" class="span1"> </div> <div id="main" class="span10"> <div id="content"> <div class="page-header"> <div class="clearfix"> <p class="lead author-list pull-left"> <span style=""> <a href="https://ir.cwi.nl/ppl/1642"> <span>J.A. Hoogeveen</span></a> </span> <br class="clearfix"/> </p> <p class="lead pub_type pull-right"> <span>1991</span> </p> </div> <h1>Analysis of Christofides' heuristic: some paths are more difficult than cycles</h1> <h2 style="display:none">Publication</h2> <h3 style="display:none">Publication</h3> <p class="lead"> <em> <a href="https://ir.cwi.nl/col/3692">Operations Research Letters</a> , Volume 10 - Issue 5 p. 291- 295 </em> </p> </div> <div class="row-fluid"> <div class="span8">  <p class="abstract"></p>  <div id="publication-metadata"> <table class="table"> <thead> <tr><th colspan="2" class="publiation-metadata-header">Additional Metadata</th></tr> </thead> <tbody> <tr> <td style="min-width:120px"> <span class="publication-metadata-key">MSC</span> </td> <td> <span class="publication-metadata-value" key="MSC">Network models, deterministic (msc 90B10)</span> </td> </tr> <tr> <td style="min-width:120px"> <span class="publication-metadata-key">Publisher</span> </td> <td> <span>North-Holland</span> </td> </tr> <tr> <td style="min-width:120px"> <span class="publication-metadata-key">Journal</span> </td> <td> <a href="https://ir.cwi.nl/col/3692">Operations Research Letters</a> </td> </tr> <tr> <td><span class="publication-metadata-key">Citation</span><br/> <div class="btn-group dropup" id="citation-menu"> <a class="btn dropdown-toggle btn-small" id="citation-menu-button" data-toggle="dropdown" href="#"> APA Style <span class="icon-chevron-up"></span> </a> <ul class="dropdown-menu"> <li> <a href="#" class="citation-style-pub" data-citation-style="aaa"> AAA Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="apa"> APA Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="cell"> Cell Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="chicago"> Chicago Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="harvard"> Harvard Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="ieee"> IEEE Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="mla"> MLA Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="nature"> Nature Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="vancouver"> Vancouver Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="american-institute-of-physics"> American-Institute-of-Physics Style </a> </li> <li> <a href="#" class="citation-style-pub" data-citation-style="council-of-science-editors"> Council-of-Science-Editors Style </a> </li> <li class="divider"/> <li> <a href="#" class="citation-format-pub" data-citation-format="bibtex"> BibTex Format </a> </li> <li> <a href="#" class="citation-format-pub" data-citation-format="endnote"> Endnote Format </a> </li> <li> <a href="#" class="citation-format-pub" data-citation-format="ris"> RIS Format </a> </li> <li> <a href="#" class="citation-format-pub" data-citation-format="csl"> CSL Format </a> </li> <li> <a href="#" class="citation-format-pub" data-citation-format="dois only"> DOIs only Format </a> </li> </ul> </div> </td> <td id="citation-text"> <div class="csl-bib-body"><div class="csl-entry">Hoogeveen, J. A. (1991). Analysis of Christofides' heuristic: some paths are more difficult than cycles. <em>Operations Research Letters</em>, <em>10</em>(5), 291–295.</div></div> </td> </tr> </tbody> </table> </div> </div> <div class="span4"> <div class="publication-downloads"> <legend> <a href="https://ir.cwi.nl/pub/2347/Fulltext" target="_blank"> <span class="icon-download-alt"></span> <span class="download-link-text"> Free Full Text </span> <small class="download-link-info"> ( Final Version ) </small> </a> </legend> </div> <div> <br/> <table class="table" id="additional_assets_table"> <thead> <tr><th colspan="2">Additional Files</th></tr> </thead> <tbody> <tr> <td> <span class="icon-external-link"></span> <a href="https://ir.cwi.nl/pub/2347/Publisher%20Version" target="_blank"> <span>Publisher Version</span> </a> <span class="pull-right"> </span> </td> </tr> <tr> <td> <span class="icon-book"></span> <a href="https://ir.cwi.nl/pub/2347/2347D.pdf"> <span>2347D.pdf</span> </a> <span class="pull-right"> Final Version , 1mb </span> </td> </tr> </tbody> </table> </div> <br/> </div> </div> </div> </div> <div id="main-right" class="span1"> </div> </div> </div> <footer class="footer row-fluid"> <div class="span10 offset1"> <div class="row-fluid"> <div class="span3"> <a> <img alt="university website" src="https://ir.cwi.nl//cwi.png"/> </a> <ul class="unstyled"> </ul> </div> <div class="span3"> <ul class="unstyled"> <li> <div> <h4>Address</h4> <ul class="unstyled" style="margin-left:0"> <li> <div class="lead" style="margin:4px"> <a href="http://www.cwi.nl"> Centrum Wiskunde & Informatica </a> </div> </li> <li> <div class="lead" style="margin:4px"> <a href="http://www.cwi.nl"> Science Park 123 | 1098 XG Amsterdam | the Netherlands </a> </div> </li> </ul> </div> </li> </ul> </div> <div class="span3"> <ul class="unstyled"> <li> <div> <h4>CWI researchers</h4> <ul class="unstyled" style="margin-left:0"> <li> <div class="lead" style="margin:4px"> <a href="/page/1"> <span class="icon-file"></span> Register Your Work </a> </div> </li> </ul> </div> </li> <li> <div> <h4>Questions or comments?</h4> <ul class="unstyled" style="margin-left:0"> <li> <div class="lead" style="margin:4px"> <a href="mailto:repository@cwi.nl"> <span class="icon-envelope"></span> repository@cwi.nl </a> </div> </li> </ul> </div> </li> </ul> </div> </div> </div> <div class="span1"> <a href="http://www.artudis.com" class="pull-right" style="margin: 170px 20px 10px 10px"> <img src="/static/img/logo/artudis_small.png" width="100" alt="artudis website"/> </a> </div> </footer> <div id="modal-workflow-editor" class="modal hide fade"> <div class="modal-header"> <button type="button" class="close" data-dismiss="modal" aria-hidden="true">×</button> <h3 id="modal-workflow-header">Workflow</h3> </div> <div id="modal-workflow-form"></div> </div> <div id="modal-iframe" style="width:800px" class="modal hide fade"> <div class="modal-header"> <button type="button" class="close" data-dismiss="modal" aria-hidden="true">×</button> <h3 id="modal-iframe-header">Workflow</h3> </div> <div> <iframe id="modal-iframe-body" src="" style="width:100%;height:500px" frameborder="0" ></iframe> </div> </div> <div id="add-content-modal" class="modal hide fade"> <div class="modal-header"> <button type="button" class="close" data-dismiss="modal" aria-hidden="true">×</button> <h3 id="modal-edit-header">Add Content</h3> </div> <div class="modal-body"> <div class="btn-group btn-group-vertical" style="width:100%;max-height:600px;overflow:auto"> <br/> <a class="btn btn-large" style="margin:auto;width:300px" href="https://ir.cwi.nl/user/add">User</a> <a class="btn btn-large" style="margin:auto;width:300px" href="https://ir.cwi.nl/pub/add">Publication</a> <a class="btn btn-large" style="margin:auto;width:300px" href="https://ir.cwi.nl/ppl/add">Person</a> <a class="btn btn-large" style="margin:auto;width:300px" href="https://ir.cwi.nl/org/add">Organisation</a> <a class="btn btn-large" style="margin:auto;width:300px" href="https://ir.cwi.nl/col/add">Collection</a> </div> </div> <div class="modal-footer"> <a href="#" class="btn btn-primary" data-dismiss="modal">Close</a> </div> </div> </body> </html>

CINXE.COM

Centrum Wiskunde & Informatica: Analysis of Christofides' heuristic: some paths are more difficult than cycles