Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Trapezoidal Rule01:26

Trapezoidal Rule

185
Estimating the distance traveled by a vehicle using its recorded velocity over time is a common problem in physics and engineering. When velocity data is available at discrete time intervals, rather than as a continuous function, numerical integration methods such as the trapezoidal rule are often employed to approximate the total displacement.The trapezoidal rule works by dividing the total time interval into several equal segments. Within each segment, the recorded velocities at the endpoints...
185
Design Example: Traverse Angle Computations01:25

Design Example: Traverse Angle Computations

413
Traverse angle computations are a critical component of surveying, used to compute the internal angles within a closed traverse. A traverse consists of a series of connected lines forming a closed loop, often used for land boundary delineation or mapping. Calculating the internal angles ensures accuracy in the traverse geometry and is essential for checking survey data integrity.The process begins with known azimuths and bearings of the traverse sides. Internal angles at each vertex are...
413
The Distance Formula01:20

The Distance Formula

775
In geometry, measuring the direct distance between two points on a plane is essential in various practical and theoretical applications. Whether in navigation, engineering, or computer graphics, determining the shortest path between two locations involves using the distance formula. This formula is derived from the Pythagorean Theorem, which relates the lengths of the sides of a right triangle. On a coordinate plane, the horizontal and vertical distances between two points serve as the legs of...
775
Area Computation by the Alternative Coordinate Method01:24

Area Computation by the Alternative Coordinate Method

788
The alternative coordinate method, also known as the Shoelace Formula, is a technique for determining the area of a traverse using Cartesian coordinates. This method relies on the sequential arrangement of x and y coordinates for each point of the shape, ensuring accuracy and ease of application.In this approach, each corner's x and y coordinates are listed as fractions, with the x-coordinate as the numerator and the y-coordinate as the denominator. These coordinates are arranged sequentially...
788
Optimization Problems01:26

Optimization Problems

185
Optimization problems often involve identifying maximum or minimum values under specific constraints. A well-known example is determining the longest horizontal pipe that can be moved around a right-angled corner, where a 3-meter-wide hallway meets a 2-meter-wide hallway. This scenario, common in architectural design and industrial transport, can be understood conceptually through geometric and trigonometric reasoning.To visualize the problem, consider the pipe as a straight line that touches...
185
Design Example: Alignment of a Road Line Using GIS01:17

Design Example: Alignment of a Road Line Using GIS

415
The alignment of a road line using Geographic Information Systems (GIS) is a critical process in civil engineering, combining advanced technology with practical decision-making. This methodology begins with the collection of geospatial data, including information on land cover, geomorphology, drainage patterns, slope, and contour details. Such data is typically acquired through satellite imagery and GIS tools, offering a comprehensive understanding of the terrain.Once the data is gathered, it...
415

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Applying deep learning to right whale photo identification.

Conservation biology : the journal of the Society for Conservation Biology·2018
Same journal

FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees.

Theory of computing systems·2026
Same journal

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths.

Theory of computing systems·2026
Same journal

The Ground-Set-Cost Budgeted Maximum Coverage Problem.

Theory of computing systems·2025
Same journal

Rudin-Shapiro Sums Via Automata Theory and Logic.

Theory of computing systems·2025
Same journal

Prediction and MDL for infinite sequences.

Theory of computing systems·2024
Same journal

On Polynomial Recursive Sequences.

Theory of computing systems·2024
See all related articles

Related Experiment Video

Updated: Apr 5, 2026

Evaluation of an Exclusive Spur Dike U-Turn Design with Radar-Collected Data and Simulation
11:41

Evaluation of an Exclusive Spur Dike U-Turn Design with Radar-Collected Data and Simulation

Published on: February 1, 2020

21.1K

[Formula: see text]-Approximation for Graphic TSP.

Marcin Mucha1

  • 1Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland.

Theory of Computing Systems
|August 25, 2015
PubMed
Summary
This summary is machine-generated.

This study improves approximation algorithms for the Travelling Salesman Problem in graphic metrics. New analysis yields a better approximation factor, advancing research in combinatorial optimization.

Keywords:
Approximation algorithmsTravelling salesman problem

More Related Videos

Evaluating the Effect of Roadside Parking on a Dual-Direction Urban Street
14:55

Evaluating the Effect of Roadside Parking on a Dual-Direction Urban Street

Published on: January 20, 2023

4.5K
Trajectory Data Analyses for Pedestrian Space-time Activity Study
16:14

Trajectory Data Analyses for Pedestrian Space-time Activity Study

Published on: February 25, 2013

14.3K

Related Experiment Videos

Last Updated: Apr 5, 2026

Evaluation of an Exclusive Spur Dike U-Turn Design with Radar-Collected Data and Simulation
11:41

Evaluation of an Exclusive Spur Dike U-Turn Design with Radar-Collected Data and Simulation

Published on: February 1, 2020

21.1K
Evaluating the Effect of Roadside Parking on a Dual-Direction Urban Street
14:55

Evaluating the Effect of Roadside Parking on a Dual-Direction Urban Street

Published on: January 20, 2023

4.5K
Trajectory Data Analyses for Pedestrian Space-time Activity Study
16:14

Trajectory Data Analyses for Pedestrian Space-time Activity Study

Published on: February 25, 2013

14.3K

Area of Science:

  • Computer Science
  • Operations Research
  • Discrete Mathematics

Background:

  • The Travelling Salesman Problem (TSP) is a cornerstone in approximation algorithms.
  • Christofides's algorithm, with a [Formula: see text] approximation factor, has been the benchmark for general metrics for over 30 years.
  • The Held-Karp LP relaxation suggests a tighter integrality gap of [Formula: see text] for TSP.

Purpose of the Study:

  • To enhance the approximation factor for the Travelling Salesman Problem in graphic metrics.
  • To provide an improved analysis of existing algorithmic approaches.
  • To establish approximation bounds for the Travelling Salesman Path Problem in graphic metrics.

Main Methods:

  • Improved analysis of the Mömke and Svensson (2011) approach.
  • Focus on approximation algorithms within the domain of graphic metrics.
  • Extension to the Travelling Salesman Path Problem.

Main Results:

  • An improved approximation factor of [Formula: see text] for the TSP in graphic metrics.
  • An approximation bound of [Formula: see text] for any ε>0 for the Travelling Salesman Path Problem in graphic metrics.
  • Significant progress building upon recent advancements by Oveis Gharan et al. (2011) and Mömke and Svensson (2011).

Conclusions:

  • The refined analysis offers a tighter approximation guarantee for TSP in graphic metrics.
  • The results advance the state-of-the-art in approximation algorithms for TSP variants.
  • This work contributes to a deeper understanding of the TSP's complexity in specific metric spaces.