pith. sign in

arxiv: 2603.16593 · v2 · submitted 2026-03-17 · 💻 cs.RO

Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming

Adir Morgan , Kiril Solovey , Oren Salzman This is my paper

Pith reviewed 2026-05-15 10:12 UTC · model grok-4.3

classification 💻 cs.RO
keywords inspection planninggraph inspection planningmixed integer linear programmingnetwork flowbranch and cutrobot path planningscalabilitypoints of interest
0
0 comments X

The pith

Reformulating graph inspection planning as network flow yields MILP models that scale to 15,000 vertices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to recast the coverage and connectivity requirements of graph inspection planning as network-flow constraints inside a mixed-integer linear program. This reformulation supports a specialized Branch-and-Cut solver that produces tighter lower bounds and finds feasible solutions on far larger graphs than earlier formulations. A reader would care because inspection tasks in medicine and infrastructure routinely involve thousands of points of interest, where existing solvers run out of memory or return no useful guarantee. The method is tested on medical, infrastructure, and synthetic benchmarks up to 15,000 vertices, where it consistently narrows optimality gaps by 30-50 percent.

Core claim

The authors reformulate the POI-coverage and path-connectivity constraints of the graph inspection planning problem as a network flow inside a mixed-integer linear program and develop a Branch-and-Cut solver that exploits the combinatorial structure of flows, producing substantially tighter lower bounds and non-trivial solutions on instances with up to 15,000 vertices and thousands of points of interest.

What carries the argument

Network-flow reformulation of the coverage and connectivity constraints within the mixed-integer linear program for graph inspection planning.

If this is right

  • The flow-based MILP produces substantially tighter lower bounds than existing formulations.
  • Optimality gaps shrink by 30-50 percent on large instances.
  • Non-trivial solutions are obtained for graphs with up to 15,000 vertices and thousands of POIs.
  • Prior state-of-the-art methods typically exhaust memory or return no meaningful optimality guarantees on the same scale.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same flow encoding could be reused for other coverage-constrained path problems such as surveillance or search-and-rescue.
  • Tighter bounds from the discrete model could be lifted back to the continuous space to guide sampling refinement.
  • Online replanning becomes feasible once the solver handles thousands of vertices in seconds rather than minutes.
  • Integration with adaptive sampling that adds vertices only near uncovered POIs might further reduce memory use.

Load-bearing premise

The sampling-based discretization that turns the continuous inspection task into a graph problem is assumed to preserve coverage and connectivity well enough for the flow model to remain valid in the original space.

What would settle it

A continuous-space test in which a solution returned by the discrete flow model leaves some point of interest uncovered due to sampling gaps would show the discretization step fails to preserve the required properties.

Figures

Figures reproduced from arXiv: 2603.16593 by Adir Morgan, Kiril Solovey, Oren Salzman.

Figure 1
Figure 1. Figure 1: Graph inspection planning using network flow. (a) The POI [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Experimental evaluation scenarios. (a) CRISP robot, composed of a snare-tube [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Solvers evaluation on real-world instances. [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Optimality gap on large-scale instances after [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Ablation study for the separation oracles reporting the final optimality gaps [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of Phase 2 of the primal heuristic for [PITH_FULL_IMAGE:figures/full_fig_p023_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of Phase 3 of the primal heuristic for [PITH_FULL_IMAGE:figures/full_fig_p024_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Inspection planning simulation. (a) The simulation environment is a planar [PITH_FULL_IMAGE:figures/full_fig_p025_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Optimality gap on small-scale simulated instances after [PITH_FULL_IMAGE:figures/full_fig_p026_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Heuristic evaluation. (a) Tour cost comparison at the root of the BnC tree. Tour costs on CRISP instances are scaled by 1, 000×. (b) Execution runtime in seconds. [41], referred to as the ST heuristic. The ST heuristic first selects vertices greed￾ily based on proximity to the root by finding the appropriate shortest-paths, until a group-covering set is obtained, then constructs a Steiner tree using a min… view at source ↗
Figure 11
Figure 11. Figure 11: Anytime performance on the Bridge-1000 instance. The plot shows the tour cost improvement over time for the different heuristics. In contrast, our GIP heuristic builds the group-covering tree iteratively, min￾imizing the incremental edge cost while covering new groups. This integrates vertex selection and tree construction into a single phase, which tends to yield more compact covering trees. Furthermore,… view at source ↗
read the original abstract

Inspection planning is concerned with computing the shortest robot path to inspect a given set of points of interest (POIs) using the robot's sensors. This problem arises in a wide range of applications from manufacturing to medical robotics. To alleviate the problem's complexity, recent methods rely on sampling-based methods to obtain a more manageable (discrete) graph inspection planning (GIP) problem. Unfortunately, GIP still remains highly difficult to solve at scale as it requires simultaneously satisfying POI-coverage and path-connectivity constraints, giving rise to a challenging optimization problem, particularly at scales encountered in real-world scenarios. In this work, we present highly scalable Mixed Integer Linear Programming (MILP) solutions for GIP that significantly advance the state-of-the-art in both runtime and solution quality. Our key insight is a reformulation of the problem's core constraints as a network flow, which enables effective MILP models and a specialized Branch-and-Cut solver that exploits the combinatorial structure of flows. We evaluate our approach on medical and infrastructure benchmarks alongside large-scale synthetic instances. Across all scenarios, our method produces substantially tighter lower bounds than existing formulations, reducing optimality gaps by 30-50% on large instances. Furthermore, our solver demonstrates unprecedented scalability: it provides non-trivial solutions for problems with up to 15,000 vertices and thousands of POIs, where prior state-of-the-art methods typically exhaust memory or fail to provide any meaningful optimality guarantees.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a network-flow reformulation of the Graph Inspection Planning (GIP) problem obtained by sampling-based discretization of continuous inspection tasks. POI coverage and path-connectivity constraints are encoded via standard flow-conservation equalities inside a MILP, solved by a custom Branch-and-Cut procedure that exploits the flow structure. Experiments on medical, infrastructure, and large synthetic instances report 30-50% reductions in optimality gaps relative to prior formulations and non-trivial feasible solutions on graphs with up to 15,000 vertices and thousands of POIs.

Significance. If the empirical bound improvements and scaling results are reproducible, the work supplies a practically useful MILP encoding for a core robotic planning primitive. The flow-based modeling is a direct, non-circular application of network-flow techniques that demonstrably enlarges the solvable instance size; this is a concrete, falsifiable advance over existing GIP solvers.

major comments (2)
  1. [§3] §3 (Flow-based MILP): the validity of the lower bounds rests on the claim that the sampling discretization preserves coverage and connectivity; however, no formal statement or quantitative bound is given on the approximation error introduced by the sampling procedure, which directly affects whether the reported optimality gaps are with respect to the original continuous problem or only the discrete proxy.
  2. [Experiments] Experimental section: the abstract states 30-50% gap reductions and scalability to 15k vertices, yet the manuscript provides neither the precise instance-generation parameters, the exact set of competing formulations, nor the termination criteria and memory limits used for the baselines; without these, the central scalability claim cannot be independently verified.
minor comments (2)
  1. [§3] Notation for flow variables and coverage indicators should be introduced once and used uniformly; several equations reuse the same symbol for distinct quantities.
  2. [Experiments] Figure captions for the scalability plots should state the number of random seeds and report both median and worst-case runtimes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive review and the recommendation for minor revision. The comments identify opportunities to strengthen clarity regarding discretization and experimental reproducibility. We address each point below and will incorporate the suggested changes in the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (Flow-based MILP): the validity of the lower bounds rests on the claim that the sampling discretization preserves coverage and connectivity; however, no formal statement or quantitative bound is given on the approximation error introduced by the sampling procedure, which directly affects whether the reported optimality gaps are with respect to the original continuous problem or only the discrete proxy.

    Authors: We thank the referee for highlighting this distinction. The GIP formulation in the paper is defined on the discrete graph produced by the sampling-based discretization step, which is a standard preprocessing technique in sampling-based planning. All optimality gaps and lower bounds reported are with respect to this discrete instance, consistent with prior GIP literature. The sampling procedure itself is external to the MILP and follows established methods without introducing additional approximation claims in our contribution. We agree that an explicit clarification would improve readability and will add a short paragraph in Section 3 stating that the MILP solves the discretized GIP exactly and that gaps are relative to the discrete proxy. revision: yes

  2. Referee: [Experiments] Experimental section: the abstract states 30-50% gap reductions and scalability to 15k vertices, yet the manuscript provides neither the precise instance-generation parameters, the exact set of competing formulations, nor the termination criteria and memory limits used for the baselines; without these, the central scalability claim cannot be independently verified.

    Authors: We acknowledge the need for greater detail to support independent verification. In the revised manuscript we will expand the experimental section (and add a dedicated appendix if space is limited) to include: (i) full instance-generation parameters (graph sizes, POI counts and densities, sampling densities, and random seeds where applicable), (ii) the complete list of baseline formulations with citations, and (iii) the precise termination criteria (time limits, optimality gap tolerances) and memory limits applied uniformly to all solvers. These additions will make the reported 30-50% gap reductions and scalability results fully reproducible. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper describes a direct MILP reformulation of the discretized graph inspection planning problem by encoding coverage and connectivity via standard network-flow conservation constraints. No equations or claims reduce the reported bound improvements or scalability results to fitted parameters, self-definitions, or self-citation chains; the performance gains are presented strictly as empirical outcomes on benchmark instances. The modeling steps rely on well-established flow-based MILP techniques without importing uniqueness theorems or ansatzes from prior author work, and the derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard graph theory flow conservation and MILP integrality assumptions plus the modeling choice that coverage and connectivity can be expressed as flow constraints; no new entities or fitted parameters are introduced in the abstract.

axioms (2)
  • domain assumption Flow conservation and capacity constraints correctly encode path connectivity and POI coverage in the discretized graph.
    Invoked when reformulating GIP constraints as network flow in the MILP model.
  • standard math Standard MILP solvers and branch-and-cut techniques can exploit the flow structure for improved performance.
    Basis for the specialized solver claim.

pith-pipeline@v0.9.0 · 5558 in / 1350 out tokens · 43762 ms · 2026-05-15T10:12:13.046468+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages

  1. [1]

    Prentice hall, 1994

    Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin.Network flows: theory, algorithms and applications. Prentice hall, 1994

    work page 1994

  2. [2]

    Con- tinuum reconfigurable parallel robots for surgery: Shape sensing and state estimation with uncertainty.IEEE robotics and automation letters, 2(3): 1617–1624, 2017

    Patrick L Anderson, Arthur W Mahoney, and Robert James Webster. Con- tinuum reconfigurable parallel robots for surgery: Shape sensing and state estimation with uncertainty.IEEE robotics and automation letters, 2(3): 1617–1624, 2017

    work page 2017

  3. [3]

    Tsp cuts which do not conform to the template paradigm

    David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. Tsp cuts which do not conform to the template paradigm. InComputational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions, pages 261–303. Springer, 2001

    work page 2001

  4. [4]

    The traveling salesman problem: a computational study

    David L Applegate, Robert E Bixby, Vašek Chvátal, and William J Cook. The traveling salesman problem: a computational study. InThe Traveling Salesman Problem. Princeton university press, 2011

    work page 2011

  5. [5]

    Uniform coverage of automotive surface patches.The In- ternational Journal of Robotics Research, 24(11):883–898, 2005

    Prasad N Atkar, Aaron Greenfield, David C Conner, Howie Choset, and Alfred A Rizzi. Uniform coverage of automotive surface patches.The In- ternational Journal of Robotics Research, 24(11):883–898, 2005

    work page 2005

  6. [6]

    A feasibility pump heuristic for general mixed-integer problems.Discrete Optimization, 4(1): 63–76, 2007

    Livio Bertacco, Matteo Fischetti, and Andrea Lodi. A feasibility pump heuristic for general mixed-integer problems.Discrete Optimization, 4(1): 63–76, 2007

    work page 2007

  7. [7]

    north-Holland, 1979

    John Adrian Bondy and Uppaluri Siva Ramachandra Murty.Graph theory with applications. north-Holland, 1979

    work page 1979

  8. [8]

    A greedy approximation algorithm for the group steiner problem.Discrete Applied Mathematics, 154 (1):15–34, 2006

    Chandra Chekuri, Guy Even, and Guy Kortsarz. A greedy approximation algorithm for the group steiner problem.Discrete Applied Mathematics, 154 (1):15–34, 2006

    work page 2006

  9. [9]

    Time-optimal uav trajec- tory planning for 3d urban structure coverage

    Peng Cheng, James Keller, and Vijay Kumar. Time-optimal uav trajec- tory planning for 3d urban structure coverage. In2008 IEEE/RSJ Inter- national Conference on Intelligent Robots and Systems, pages 2750–2757. IEEE, 2008

    work page 2008

  10. [10]

    Efficient and accurate mapping of subsurface anatomy via online trajectory optimization for robot assisted surgery

    Brian Y Cho and Alan Kuntz. Efficient and accurate mapping of subsurface anatomy via online trajectory optimization for robot assisted surgery. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pages 15478–15484. IEEE, 2024

    work page 2024

  11. [11]

    Planning sensing sequences for subsurface 3d tumor mapping

    Brian Y Cho, Tucker Hermans, and Alan Kuntz. Planning sensing sequences for subsurface 3d tumor mapping. In2021 international symposium on medical robotics (ISMR), pages 1–7. IEEE, 2021

    work page 2021

  12. [12]

    Worst-case analysis of a new heuristic for the travel- ling salesman problem

    Nicos Christofides. Worst-case analysis of a new heuristic for the travel- ling salesman problem. InOperations Research Forum, volume 3, page 20. Springer, 2022

    work page 2022

  13. [13]

    A new formulation for the travelling salesman problem.SIAM Journal on Algebraic Discrete Methods, 5(1):21–25, 1984

    A Claus. A new formulation for the travelling salesman problem.SIAM Journal on Algebraic Discrete Methods, 5(1):21–25, 1984

    work page 1984

  14. [14]

    Cook and Andre Rohe

    William J. Cook and Andre Rohe. Computing minimum-weight perfect matchings.INFORMS Journal on Computing, 11(2):138–148, 1999. 18 Morgan, Solovey, and Salzman

    work page 1999

  15. [15]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms. The MIT Press, Cambridge, MA, USA, 3 edition, 2009

    work page 2009

  16. [16]

    Exploringrelaxation induced neighborhoods to improve mip solutions.Mathematical Program- ming, 102(1):71–90, 2005

    EmilieDanna,EdwardRothberg,andClaudeLePape. Exploringrelaxation induced neighborhoods to improve mip solutions.Mathematical Program- ming, 102(1):71–90, 2005

    work page 2005

  17. [17]

    On the max flow min cut theorem of networks.Linear inequalities and related systems, 38:225–231, 2003

    George Dantzig and Delbert Ray Fulkerson. On the max flow min cut theorem of networks.Linear inequalities and related systems, 38:225–231, 2003

    work page 2003

  18. [18]

    Paths,trees,andflowers.Canadian Journal of Mathematics, 17:449–467, 1965

    JackEdmonds. Paths,trees,andflowers.Canadian Journal of Mathematics, 17:449–467, 1965

    work page 1965

  19. [19]

    Theoretical improvements in algorith- mic efficiency for network flow problems.Journal of the ACM (JACM), 19 (2):248–264, 1972

    Jack Edmonds and Richard M Karp. Theoretical improvements in algorith- mic efficiency for network flow problems.Journal of the ACM (JACM), 19 (2):248–264, 1972

    work page 1972

  20. [20]

    A threshold oflnnfor approximating set cover.Journal of the ACM, 45(4):634–652, 1998

    Uriel Feige. A threshold oflnnfor approximating set cover.Journal of the ACM, 45(4):634–652, 1998

    work page 1998

  21. [21]

    The feasibility pump

    Matteo Fischetti, Fred Glover, and Andrea Lodi. The feasibility pump. Mathematical Programming, 104(1):91–104, 2005

    work page 2005

  22. [22]

    Toward asymptotically-optimal inspection planning via efficient near-optimal graph search.Robotics science and systems: online proceedings, 2019:10–15607, 2019

    Mengyu Fu, Alan Kuntz, Oren Salzman, and Ron Alterovitz. Toward asymptotically-optimal inspection planning via efficient near-optimal graph search.Robotics science and systems: online proceedings, 2019:10–15607, 2019

    work page 2019

  23. [23]

    Computationally-efficient roadmap-based inspection planning via incremental lazy search

    Mengyu Fu, Oren Salzman, and Ron Alterovitz. Computationally-efficient roadmap-based inspection planning via incremental lazy search. In2021 IEEE International Conference on Robotics and Automation (ICRA), pages 7449–7456. IEEE, 2021

    work page 2021

  24. [24]

    Scip-jack—a solver for stp and variants with parallelization extensions.Mathematical Programming Computation, 9(2):231–296, 2017

    Gerald Gamrath, Thorsten Koch, Stephen J Maher, Daniel Rehfeldt, and Yuji Shinano. Scip-jack—a solver for stp and variants with parallelization extensions.Mathematical Programming Computation, 9(2):231–296, 2017

    work page 2017

  25. [25]

    A polylogarithmic approximation algorithm for the group steiner tree problem.Journal of Algorithms, 37(1):66–84, 2000

    Naveen Garg, Goran Konjevod, and Ramamoorthi Ravi. A polylogarithmic approximation algorithm for the group steiner tree problem.Journal of Algorithms, 37(1):66–84, 2000

    work page 2000

  26. [26]

    The travelling salesman problem and related problems

    Bezalel Gavish and Stephen C Graves. The travelling salesman problem and related problems. 1978

    work page 1978

  27. [27]

    Gurobi Optimizer Reference Manual, 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024

    work page 2024

  28. [28]

    Polylogarithmic inapproximabil- ity

    Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximabil- ity. InProceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 585–594, 2003

    work page 2003

  29. [29]

    Hwang, Dana S

    Frank K. Hwang, Dana S. Richards, and Pawel Winter.The Steiner Tree Problem. Elsevier, 1992

    work page 1992

  30. [30]

    Incremental sampling-based algo- rithms for optimal motion planning.Robotics Science and Systems VI, 104 (2):267–274, 2010

    Sertac Karaman and Emilio Frazzoli. Incremental sampling-based algo- rithms for optimal motion planning.Robotics Science and Systems VI, 104 (2):267–274, 2010

    work page 2010

  31. [31]

    Richard M. Karp. Reducibility among combinatorial problems.Complexity of Computer Computations, pages 85–103, 1972. Scalable Inspection Planning via Flow-based MILP 19

    work page 1972

  32. [32]

    Karp and Michael Sipser

    Richard M. Karp and Michael Sipser. Maximum matching in sparse random graphs. InProceedings of the 22nd Annual Symposium on Foundations of Computer Science, pages 364–375, 1981

    work page 1981

  33. [33]

    Solving Steiner tree problems in graphs to optimality.Networks: An International Journal, 32(3):207–232, 1998

    Thorsten Koch and Alexander Martin. Solving Steiner tree problems in graphs to optimality.Networks: An International Journal, 32(3):207–232, 1998

    work page 1998

  34. [34]

    An automatic method for solving discrete programming problems

    Ailsa H Land and Alison G Doig. An automatic method for solving discrete programming problems. In50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, pages 105–132. Springer, 2009

    work page 1958

  35. [35]

    Generalized travelling salesman prob- lem through n sets of nodes: an integer programming approach.INFOR: Information Systems and Operational Research, 21(1):61–75, 1983

    Gilbert Laporte and Yves Nobert. Generalized travelling salesman prob- lem through n sets of nodes: an integer programming approach.INFOR: Information Systems and Operational Research, 21(1):61–75, 1983

    work page 1983

  36. [36]

    Branch-and-boundmethods:Asurvey

    EugeneLLawlerandDavidEWood. Branch-and-boundmethods:Asurvey. Operations research, 14(4):699–719, 1966

    work page 1966

  37. [37]

    Lawler, Jan Karel Lenstra, Alexander H

    Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, and David B. Shmoys.The Traveling Salesman Problem. Wiley, 1985

    work page 1985

  38. [38]

    Reconfigurable parallel continuum robots for incisionless surgery

    Arthur W Mahoney, Patrick L Anderson, Philip J Swaney, Fabien Mal- donado, and Robert J Webster. Reconfigurable parallel continuum robots for incisionless surgery. In2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4330–4336. IEEE, 2016

    work page 2016

  39. [39]

    Integer program- ming formulation of traveling salesman problems.Journal of the ACM (JACM), 7(4):326–329, 1960

    Clair E Miller, Albert W Tucker, and Richard A Zemlin. Integer program- ming formulation of traveling salesman problems.Journal of the ACM (JACM), 7(4):326–329, 1960

    work page 1960

  40. [40]

    Branch-and-cut algorithms for combinatorial optimization problems.Handbook of applied optimization, 1(1):65–77, 2002

    John E Mitchell. Branch-and-cut algorithms for combinatorial optimization problems.Handbook of applied optimization, 1(1):65–77, 2002

    work page 2002

  41. [41]

    Lever- aging fixed-parameter tractability for robot inspection planning.arXiv preprint arXiv:2407.00251, 2024

    Yosuke Mizutani, Daniel Coimbra Salomao, Alex Crane, Matthias Bentert, Pål Grønås Drange, Felix Reidl, Alan Kuntz, and Blair D Sullivan. Lever- aging fixed-parameter tractability for robot inspection planning.arXiv preprint arXiv:2407.00251, 2024

    work page arXiv 2024

  42. [42]

    A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems.SIAM review, 33(1):60–100, 1991

    Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems.SIAM review, 33(1):60–100, 1991

    work page 1991

  43. [43]

    Effectivesamplingforrobotmotionplanning through the lens of lattices

    ItaiPanasoffandKirilSolovey. Effectivesamplingforrobotmotionplanning through the lens of lattices. InRobotics: Science and Systems, 2025

    work page 2025

  44. [44]

    P-complete approximation problems

    Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM, 23(3):555–565, 1976

    work page 1976

  45. [45]

    An approximate solution for steiner problem in graphs.Math

    Hiromitsu Takahashi. An approximate solution for steiner problem in graphs.Math. Japonica, 24(6):573–577, 1980

    work page 1980

  46. [46]

    Vazirani.Approximation Algorithms

    Vijay V. Vazirani.Approximation Algorithms. Springer, 2001

    work page 2001

  47. [47]

    Integer programming formulations of the traveling sales- man problem

    Richard T Wong. Integer programming formulations of the traveling sales- man problem. InProceedings of the IEEE international conference of cir- cuits and computers, volume 149, page 152. IEEE Press Piscataway NJ, 1980. 20 Morgan, Solovey, and Salzman A Approximation Bounds for Graph Inspection Planning Inthissection,weleveragetheconnectionbetweenGIPandGr...

    work page 1980

  48. [48]

    Covering-Tree

    Thm. 4 stated a straight forwardO(k)-approximation algorithm. To the best of our knowledge, approximation lower bounds have not previously been established forGIP.4 We begin by restating the following approximation bounds forGroup-ST. Below,kdenotes the number of groups, andn=|V|. Theorem 1 (Lower approximation bounds forGroup-ST[28]).Group- STis hard 5 t...

    work page 2000