@article{BKS17,
  title =	 {A parameterized approximation algorithm for the
                  mixed and windy Capacitated Arc Routing Problem:
                  theory and experiments},
  author =	 {René van Bevern and Christian Komusiewicz and Manuel
                  Sorge},
  journal =	 {Networks},
  volume =	 {70},
  number =	 {3},
  issn =	 {1097-0037},
  doi =		 {10.1002/net.21742},
  pages =	 {262--278},
  keywords =	 {vehicle routing, transportation, Rural Postman,
                  Chinese Postman, NP-hard problem, fixed-parameter
                  algorithm, combinatorial optimization},
  year =	 {2017},
  url_Preprint = {https://arxiv.org/abs/1506.05620},
  url_Slides =
                  {http://rvb.su/pdf/approximation-directed-arc-routing-atmos15.pdf},
  url_Code =	 {https://gitlab.com/rvb/mwcarp-approx},
  date =	 {2017-10-01},
  abstract =	 {We prove that any polynomial-time α(n)-approximation
                  algorithm for the n-vertex metric asymmetric
                  Traveling Salesperson Problem yields a
                  polynomial-time O(α(C))-approximation algorithm for
                  the mixed and windy Capacitated Arc Routing Problem,
                  where C is the number of weakly connected components
                  in the subgraph induced by the positive-demand
                  arcs---a small number in many applications.  In
                  conjunction with known results, we obtain
                  constant-factor approximations for C∈O(log n) and
                  O(log C/log log C)-approximations in general.
                  Experiments show that our algorithm, together with
                  several heuristic enhancements, outperforms many
                  previous polynomial-time heuristics.  Finally, since
                  the solution quality achievable in polynomial time
                  appears to mainly depend on C and since C=1 in
                  almost all benchmark instances, we propose the Ob
                  benchmark set, simulating cities that are divided
                  into several components by a river.}
}

{"_id":"4FSB4iXJgnPWWF6m2","bibbaseid":"vanbevern-komusiewicz-sorge-aparameterizedapproximationalgorithmforthemixedandwindycapacitatedarcroutingproblemtheoryandexperiments-2017","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Komusiewicz, C.","Sorge, M."],"bibdata":{"bibtype":"article","type":"article","title":"A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Christian"],"propositions":[],"lastnames":["Komusiewicz"],"suffixes":[]},{"firstnames":["Manuel"],"propositions":[],"lastnames":["Sorge"],"suffixes":[]}],"journal":"Networks","volume":"70","number":"3","issn":"1097-0037","doi":"10.1002/net.21742","pages":"262–278","keywords":"vehicle routing, transportation, Rural Postman, Chinese Postman, NP-hard problem, fixed-parameter algorithm, combinatorial optimization","year":"2017","url_preprint":"https://arxiv.org/abs/1506.05620","url_slides":"http://rvb.su/pdf/approximation-directed-arc-routing-atmos15.pdf","url_code":"https://gitlab.com/rvb/mwcarp-approx","date":"2017-10-01","abstract":"We prove that any polynomial-time α(n)-approximation algorithm for the n-vertex metric asymmetric Traveling Salesperson Problem yields a polynomial-time O(α(C))-approximation algorithm for the mixed and windy Capacitated Arc Routing Problem, where C is the number of weakly connected components in the subgraph induced by the positive-demand arcs—a small number in many applications. In conjunction with known results, we obtain constant-factor approximations for C∈O(log n) and O(log C/log log C)-approximations in general. Experiments show that our algorithm, together with several heuristic enhancements, outperforms many previous polynomial-time heuristics. Finally, since the solution quality achievable in polynomial time appears to mainly depend on C and since C=1 in almost all benchmark instances, we propose the Ob benchmark set, simulating cities that are divided into several components by a river.","bibtex":"@article{BKS17,\n title =\t {A parameterized approximation algorithm for the\n mixed and windy Capacitated Arc Routing Problem:\n theory and experiments},\n author =\t {René van Bevern and Christian Komusiewicz and Manuel\n Sorge},\n journal =\t {Networks},\n volume =\t {70},\n number =\t {3},\n issn =\t {1097-0037},\n doi =\t\t {10.1002/net.21742},\n pages =\t {262--278},\n keywords =\t {vehicle routing, transportation, Rural Postman,\n Chinese Postman, NP-hard problem, fixed-parameter\n algorithm, combinatorial optimization},\n year =\t {2017},\n url_Preprint = {https://arxiv.org/abs/1506.05620},\n url_Slides =\n {http://rvb.su/pdf/approximation-directed-arc-routing-atmos15.pdf},\n url_Code =\t {https://gitlab.com/rvb/mwcarp-approx},\n date =\t {2017-10-01},\n abstract =\t {We prove that any polynomial-time α(n)-approximation\n algorithm for the n-vertex metric asymmetric\n Traveling Salesperson Problem yields a\n polynomial-time O(α(C))-approximation algorithm for\n the mixed and windy Capacitated Arc Routing Problem,\n where C is the number of weakly connected components\n in the subgraph induced by the positive-demand\n arcs---a small number in many applications. In\n conjunction with known results, we obtain\n constant-factor approximations for C∈O(log n) and\n O(log C/log log C)-approximations in general.\n Experiments show that our algorithm, together with\n several heuristic enhancements, outperforms many\n previous polynomial-time heuristics. Finally, since\n the solution quality achievable in polynomial time\n appears to mainly depend on C and since C=1 in\n almost all benchmark instances, we propose the Ob\n benchmark set, simulating cities that are divided\n into several components by a river.}\n}\n\n","author_short":["van Bevern, R.","Komusiewicz, C.","Sorge, M."],"key":"BKS17","id":"BKS17","bibbaseid":"vanbevern-komusiewicz-sorge-aparameterizedapproximationalgorithmforthemixedandwindycapacitatedarcroutingproblemtheoryandexperiments-2017","role":"author","urls":{" preprint":"https://arxiv.org/abs/1506.05620"," slides":"http://rvb.su/pdf/approximation-directed-arc-routing-atmos15.pdf"," code":"https://gitlab.com/rvb/mwcarp-approx"},"keyword":["vehicle routing","transportation","Rural Postman","Chinese Postman","NP-hard problem","fixed-parameter algorithm","combinatorial optimization"],"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":0,"html":""},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:16:51.469Z","downloads":0,"keywords":["vehicle routing","transportation","rural postman","chinese postman","np-hard problem","fixed-parameter algorithm","combinatorial optimization"],"search_terms":["parameterized","approximation","algorithm","mixed","windy","capacitated","arc","routing","problem","theory","experiments","van bevern","komusiewicz","sorge"],"title":"A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments","year":2017,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}