Rural postman approximation in cubic arithmetic time
ProvedVehicleRoutingSurvey.Routing.rpp_tree_matching_runtimegraph-theoryrural-postman
There is a fixed program in the arithmetic instruction model for the rural postman algorithm of Table 3. For every rural instance with sufficiently many vertices, the program returns a run of the spanning-tree and matching algorithm in instructions, where and count the vertices and links.
Preamble
import Definitions.Def_VehicleRoutingSurvey_Routing_RuralRuntime open VehicleRoutingSurvey.Routing
Formal statement
theorem VehicleRoutingSurvey.Routing.rpp_tree_matching_runtime : ∃ (p : List ArithmeticInstruction) (C N : ℕ), RuralImplementation p C N := by sorry
Source
J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity of vehicle routing and scheduling problems (1979), Table 3, printed p. 5. https://ir.cwi.nl/pub/9658/9658D.pdf