A (3/2+1/e)-approximation algorithm for ordered TSP
From MaRDI portal
A \((3/2+1/e)\)-approximation algorithm for ordered TSP
Cites work
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- A (slightly) improved approximation algorithm for metric TSP
- A (3/2+1/e)-approximation algorithm for ordered TSP
- A better-than-1.6-approximation for prize-collecting TSP
- A comment on scheduling on uniform machines under chain-type precedence constraints
- A deterministic better-than-3/2 approximation algorithm for metric TSP
- A Reduction Method for Edge-Connectivity in Graphs
- An improved approximation guarantee for prize-collecting TSP
- Approximation schemes for scheduling jobs with chain precedence constraints
- Bounds on Multiprocessing Timing Anomalies
- Complexity results for scheduling chains on a single machine
- Conditional hardness of precedence constrained scheduling on identical machines
- Constrained TSP and low-power computing
- Heuristic analysis, linear programming and branch and bound
- scientific article; zbMATH DE number 3746840 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improved approximations for TSP with simple precedence constraints
- New inapproximability bounds for TSP
- Nonpreemptive LP-Scheduling on Homogeneous Multiprocessor Systems
- On a theorem of Mader
- On extended formulations for the precedence constrained asymmetric traveling salesman problem
- On some connectivity properties of Eulerian graphs
- On the Approximation Hardness of Some Generalizations of TSP
- Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
- Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
- Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization
- Scheduling chain-structured tasks to minimize makespan and mean flow time
- Scheduling with communication delays via LP hierarchies and clustering
- Solution of a Large-Scale Traveling-Salesman Problem
- The precedence-constrained asymmetric traveling salesman polytope
- The Traveling Salesman Problem with Distances One and Two
- The traveling salesman problem with few inner points
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Worst-case analysis of a new heuristic for the travelling salesman problem
Cited in
(3)
This page was built for publication: A \((3/2+1/e)\)-approximation algorithm for ordered TSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6920846)
