Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

DOI10.1007/S10107-013-0631-6zbMATH Open1327.90121OpenAlexW2129480990MaRDI QIDQ2452379FDOQ2452379

Authors: Alejandro Toriello 

Publication date: 2 June 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-013-0631-6

Recommendations

• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• Approximation algorithms for the bottleneck asymmetric traveling salesman problem
• Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
• An optimal scheme for toll pricing problem
• The effect of the asymmetry of road transportation networks on the traveling salesman problem
• The research of optimal down bound of asymmetrical TSP
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem

zbMATH Keywords

traveling salesman problemdynamic programinteger programlower bound techniqueapproximate linear program

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Dynamic programming (90C39) Integer programming (90C10)

Cites Work

• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• A Dynamic Programming Approach to Sequencing Problems
• The traveling salesman problem and its variations
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Generalized polynomial approximations in Markovian decision processes
• Worst-case comparison of valid inequalities for the TSP
• Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints
• Heuristic analysis, linear programming and branch and bound
• A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Approximate extended formulations
• Title not available (Why is that?)
• Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
• SPLINE APPROXIMATIONS TO VALUE FUNCTIONS
• Duality and Existence of Optimal Policies in Generalized Joint Replenishment

Cited In (7)

• The research of optimal down bound of asymmetrical TSP
• Network-based approximate linear programming for discrete optimization
• A polyhedral approach to online bipartite matching
• Probabilistic prediction of the complexity of traveling salesman problems based on approximating the complexity distribution from experimental data
• A Polyhedral Approach to Online Bipartite Matching
• Analysis of the Held-Karp lower bound for the asymmetric TSP
• A bilevel programming approach to the travelling salesman problem.

Uses Software

• Concorde

This page was built for publication: Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2452379)