Approximation algorithms for some routing problems

G. Frederickson,M. Hecht,Chul E. Kim

Published 1976 in 17th Annual Symposium on Foundations of Computer Science (sfcs 1976)

ABSTRACT

No abstract is available for this paper.

PUBLICATION RECORD

Publication year
1976
Venue
17th Annual Symposium on Foundations of Computer Science (sfcs 1976)
Publication date
1976-10-25
Fields of study
Mathematics, Computer Science
Identifiers
DOI 10.1137/0207017
External record
Open on Semantic Scholar
Source metadata
Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

No claims are published for this paper.

CONCEPTS

No concepts are published for this paper.

REFERENCES

Approximation algorithms for combinatorial problems: an annotated bibliography
1976cited by this paper
Some complexity results for the Traveling Salesman Problem
1976cited by this paper
Approximate Algorithms for the 0/1 Knapsack Problem
1975cited by this paper
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
1975cited by this paper
Approximate Algorithms for the Traveling Salesperson Problem
1974cited by this paper
Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem
1974cited by this paper
Approximation algorithms for combinatorial problems
1973cited by this paper
Matching, Euler tours and the Chinese postman
1973cited by this paper
The complexity of theorem-proving procedures
1971cited by this paper
Integer Programming Formulation of Traveling Salesman Problems
1960cited by this paper

CITED BY

Minimizing Total Travel Time for Collaborative Package Delivery with Heterogeneous Drones
2026influential citation
Improved Approximations for Dial-a-Ride Problems
2026cites this paper
Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
2025cites this paper
Approximation algorithms for solving the heterogeneous rooted tree/path cover problems
2025influential citation
Scheduling on Identical Machines with Setup Time and Unknown Execution Time
2025cites this paper
Maximizing Rides Served for Dial-a-Ride on the Uniform Metric
2025cites this paper
Discrete Starfish Optimization Algorithm for Symmetric Travelling Salesman Problem
2025cites this paper
Multi-Robot Path Planning Algorithm for Collaborative Mapping under Communication Constraints
2024cites this paper
Single- and Multi-Depot Optimization for UAV-Based IoT Data Collection in Neighborhoods
2024cites this paper
A Two-Stage Reactive Auction Framework for the Multi-Depot Rural Postman Problem with Dynamic Vehicle Failures
2024cites this paper
Supermarket-chain grocery delivery optimization through crowdshipping
2024cites this paper
An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies
2024cites this paper
Heterogeneous Min-Max Multi-Vehicle Multi-Depot Traveling Salesman Problem: Heuristics and Computational Results
2024cites this paper
Maximizing the number of rides served for time-limited Dial-a-Ride*
2024cites this paper
Critical-edge based tabu search algorithm for solving large-scale multi-vehicle Chinese postman problem
2024cites this paper
Automated mission planning for aerial large‐scale power plant thermal inspection
2024cites this paper
Approximation algorithms for two clustered arc routing problems
2024cites this paper
Approximation algorithms for solving the trip-constrained vehicle routing cover problems
2024cites this paper
Hybrid Metaheuristic Approaches for the Multi-Depot Rural Postman Problem With Rechargeable and Reusable Vehicles
2024cites this paper
Approximation algorithms for the restricted k-Chinese postman problems with penalties
2023influential citation
Approximation Algorithms for the Min–Max Mixed Rural Postmen Cover Problem and Its Variants
2023influential citation
A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots
2023cites this paper
Solving the Min-Max Clustered Traveling Salesmen Problem Based on Genetic Algorithm
2023cites this paper
Evaluation of a Team-Based Collection and Delivery Operation
2023cites this paper
An approximation algorithm for the clustered path travelling salesman problem
2023cites this paper
Earliest Deadline First Is a 2-Approximation for DARP with Time Windows
2023influential citation
Efficient Package Delivery Task Assignment for Truck and High Capacity Drone
2023cites this paper
Bounds on Optimal Revisit Times in Persistent Monitoring Missions With a Distinct and Remote Service Station
2023cites this paper
Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
2023cites this paper
A Survey on Task Allocation and Scheduling in Robotic Network Systems
2023cites this paper
Approximation Algorithms for Solving the k-Chinese Postman Problem Under Interdiction Budget Constraints
2023cites this paper
Achieving feasibility for clustered traveling salesman problems using PQ‐trees
2023cites this paper
Multi-trip algorithm for multi-depot rural postman problem with rechargeable vehicles
2023cites this paper
A Computation Investigation of the Impact of Convex Hull subtour on the Nearest Neighbour Heuristic
2023cites this paper
Autonomous Multirobot Navigation and Cooperative Mapping in Partially Unknown Environments
2023cites this paper
The single robot line coverage problem: Theory, algorithms, and experiments
2022cites this paper
Line Coverage With Multiple Robots: Algorithms and Experiments
2022cites this paper
Approximation algorithms for the min-max clustered k-traveling salesmen problems
2022cites this paper
Minimizing the Longest Tour Time Among a Fleet of UAVs for Disaster Area Surveillance
2022cites this paper
New Approximation Algorithms for the Rooted Budgeted Cycle Cover Problem
2022cites this paper
Online Scheduling on Identical Machines with a Metric State Space
2022cites this paper
An Effective Iterated Two-stage Heuristic Algorithm for the Multiple Traveling Salesmen Problem
2022cites this paper
Approximation Algorithms for Multi-vehicle Stacker Crane Problems
2022influential citation
Data collection in wireless sensor networks by ground robots with full freedom
2022cites this paper
Data extraction in network through Rendezvous Point network
2022cites this paper
Approximation algorithms for some min–max and minimum stacker crane cover problems
2022influential citation
Approximation algorithms for some Minimum Postmen Cover Problems
2022cites this paper
Approximation algorithms for solving the heterogeneous Chinese postman problem
2022cites this paper
Multi-Depot Multi-Trip Vehicle Routing with Total Completion Time Minimization
2022cites this paper
An asymptotically tight online algorithm for m-Steiner Traveling Salesman Problem
2022cites this paper
Efficient Approximations for Many-Visits Multiple Traveling Salesman Problems
2022cites this paper
An overview of graph covering and partitioning
2022cites this paper
Approximations for Many-Visits Multiple Traveling Salesman Problems
2022cites this paper
Gossiping by energy-constrained mobile agents in tree networks
2021cites this paper
On-demand Robotic Fleet Routing in Capacitated Networks with Time-varying Transportation Demand
2021cites this paper
Modeling and optimization of multiple traveling salesmen problems: An evolution strategy approach
2021cites this paper
Solving vehicle routing problems with stochastic and correlated travel times and makespan objectives
2021cites this paper
Modeling and Solving the Intersection Inspection Rural Postman Problem
2021cites this paper
The m-Steiner Traveling Salesman Problem with online edge blockages
2021cites this paper
Approximation algorithms for some min–max postmen cover problems
2021cites this paper
Genetic and Ant Colony Algorithms to Solve the Multi-TSP
2021cites this paper
An Approximation Algorithm for Solving the Heterogeneous Chinese Postman Problem
2021cites this paper
The min-max close-enough arc routing problem
2021cites this paper
A Special Case of the Multiple Traveling Salesmen Problem in End-of-Aisle Picking Systems
2021cites this paper
An improved shuffled frog-leaping algorithm for the minmax multiple traveling salesman problem
2021cites this paper
Min-Max Task Assignment and Sequencing with Heterogeneous Unmanned Vehicles
2021influential citation
Minimizing the Maximum Charging Delay of Multiple Mobile Chargers Under the Multi-Node Energy Charging Scheme
2021cites this paper
Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity
2020cites this paper
A Construction Tour Technique For Solving The Travelling Salesman Problem Based On Convex Hull And Nearest Neighbour Heuristics
2020cites this paper
Min-Max Tours and Paths for Task Allocation to Heterogeneous Agents
2020influential citation
The traveling salesman puts-on a hard hat - Tower crane scheduling in construction projects
2020cites this paper
New LP relaxations for Minimum Cycle/Path/Tree Cover Problems
2020cites this paper
Online Search with Maximum Clearance
2020influential citation
Preemptive stacker crane problem: Extending tree-based properties and construction heuristics
2020cites this paper
Miniature Robot Path Planning for Bridge Inspection: Min-Max Cycle Cover-Based Approach
2020cites this paper
Plowing with precedence in polynomial time
2020cites this paper
Multirobot Coverage of Linear Modular Environments
2020influential citation
Particle Swarm Optimization for Cooperative Multi-Robot Task Allocation: A Multi-Objective Approach
2020cites this paper
Approximation Algorithms for the Min-Max Cycle Cover Problem With Neighborhoods
2020cites this paper
Energy-Efficient Elevating Transfer Vehicle Routing for Automated Multi-Level Material Handling Systems
2020influential citation
Multi-UAV Surveillance With Minimum Information Idleness and Latency Constraints
2020cites this paper
Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles
2020cites this paper
Planning for Aerial Robot Teams for Wide-Area Biometric and Phenotypic Data Collection
2020cites this paper
Multirobot Coverage of Modular Environments
2020influential citation
IMPROVING APPROXIMATION RATIOS FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM
2020influential citation
CNF Encodings for the Min-Max Multiple Traveling Salesmen Problem
2020cites this paper
Traveling Salesman Problem in a Geographic Information Management System
2020cites this paper
Arc Routing Based on the Zero-Suppressed Binary Decision Diagram
2020cites this paper
Approximation algorithms for general cluster routing problem
2020influential citation
Risk-Aware Submodular Optimization for Stochastic Travelling Salesperson Problem
2020cites this paper
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
2020cites this paper
Distributed multi‐vehicle task assignment in a time‐invariant drift field with obstacles
2019cites this paper
A Novel Cooperative Path Planning for Multi-robot Persistent Coverage with Obstacles and Coverage Period Constraints
2019cites this paper
Efficient Large-Scale Multi-Drone Delivery Using Transit Networks
2019cites this paper
A Genetic Algorithm for MinMax k-Chinese Postman Problem with Applications to Bridge Inspection
2019cites this paper
Institutional Knowledge at Singapore Management University Institutional Knowledge at Singapore Management University Bucket Brigades on In-Tree Assembly Networks Bucket Brigades on In-Tree Assembly Networks
2019influential citation
Toward Fast and Optimal Robotic Pick-and-Place on a Moving Conveyor
2019cites this paper
Trajectory Planning for Reconnaissance Mission Based on Fair-Energy UAVs Cooperation
2019cites this paper
Persistent Multi-UAV Surveillance with Data Latency Constraints
2019cites this paper
Relax, Round, Reformulate : Near-Optimal Algorithms for Planning Problems in Network Design and Scheduling
2019cites this paper