Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Covering Path Problem on a Grid   This paper introduces the covering path problem on a grid (CPPG) which finds
the cost-minimizing path connecting a subset of points in a grid such that each
point that needs to be covered is within a predetermined distance of a point
from the chosen subset. We leverage the geometric properties of the grid graph
which captures the road network structure in many transportation problems,
including our motivating setting of school bus routing. As defined in this
paper, the CPPG is a bi-objective optimization problem comprised of one cost
term related to path length and one cost term related to stop count. We develop
a trade-off constraint which quantifies the trade-off between path length and
stop count and provides a lower bound for the bi-objective optimization
problem. We introduce simple construction techniques to provide feasible paths
that match the lower bound within a constant factor. Importantly, this solution
approach uses transformations of the general CPPG to either a discrete CPPG or
continuous CPPG based on the value of the coverage radius. For both the
discrete and continuous versions, we provide fast constant-factor
approximations, thus solving the general CPPG.

0
The categories of this paper are: hep-ph
31
The categories of this paper are: ao-sci
15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
27
The categories of this paper are: comp-gas
1
The categories of this paper are: cs
23
The categories of this paper are: solv-int
22
The categories of this paper are: chao-dyn
6
The categories of this paper are: astro-ph
4
The categories of this paper are: cond-mat
21
The categories of this paper are: adap-org
36
The categories of this paper are: cmp-lg
32
The categories of this paper are: atom-ph
37
The categories of this paper are: supr-con
7
The categories of this paper are: hep-th
8
The categories of this paper are: hep-ex