Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Related Concept Videos

Flat Belts: Problem Solving

Flat Belts: Problem Solving

Flat belts are crucial in many industrial applications as they help transmit power from one pulley to another. The concept of forces and moments is used to determine the maximum moment on a pulley. For instance, consider a flat belt that wraps around two pulleys, A and B, with radii of 30 cm and 10 cm, respectively. The angle between the belt and the horizontal is 20 degrees at the pulleys. As pulley B rotates clockwise and drives pulley A, tension T2 is caused at one end of the belt, while...

Dot Product: Problem Solving

Dot Product: Problem Solving

The dot product is a powerful tool in problem-solving involving vectors, given that the dot product of two vectors is the product of their magnitudes and the cosine of the angle between them measured anti-clockwise. Solving problems involving the dot product requires understanding its properties and developing a step-by-step process to solve them. Here are the main steps to follow when solving any general problem involving the dot product:
Identify the problem: Start by reading the problem and...

Gaussian Elimination: Problem Solving

Gaussian Elimination: Problem Solving

Systems of linear equations in several variables are pivotal in modeling complex scenarios involving multiple unknowns and constraints. Such systems are widely used in various fields to represent relationships where several conditions must be simultaneously satisfied. Each variable in the system corresponds to an unknown quantity, while each equation imposes a linear constraint, leading to a structured approach for analyzing and solving real-world problems.A system of three equations with three...

Trapezoidal Rule

Trapezoidal Rule

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...

Collisions in Multiple Dimensions: Problem Solving

Collisions in Multiple Dimensions: Problem Solving

In multiple dimensions, the conservation of momentum applies in each direction independently. Hence, to solve collisions in multiple dimensions, we should write down the momentum conservation in each direction separately. To help understand collisions in multiple dimensions, consider an example.
A small car of mass 1,200 kg traveling east at 60 km/h collides at an intersection with a truck of mass 3,000 kg traveling due north at 40 km/h. The two vehicles are locked together. What is the...

Statically Indeterminate Problem Solving

Statically Indeterminate Problem Solving

Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...

You might also read

Related Articles

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

Sort by

Same author

A linear time algorithm for linearizing quadratic and higher-order shortest path problems.

Mathematical programming·2025

Same author

Continuous facility location on graphs.

Mathematical programming·2022

Same author

Complexity and approximability of double digest.

Journal of bioinformatics and computational biology·2005

See all related articles

Search research articles

Related Experiment Video

Updated: Feb 17, 2026

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Published on: July 24, 2021

The multi-stripe travelling salesman problem.

Eranda Çela¹, Vladimir G Deineko², Gerhard J Woeginger³

¹Institut für Diskrete Mathematik, TU Graz, Steyrergasse 30, 8010 Graz, Austria.

Annals of Operations Research

|December 5, 2017

Summary

The q-stripe Traveling Salesman Problem (TSP) generalizes the classical TSP by summing costs to q subsequent cities. This study analyzes its computational complexity, revealing both NP-hard and polynomially solvable cases for structured distance matrices.

Keywords:

Combinatorial optimization Computational complexity Kalmanson conditions Quadratic assignment problem Tractable special case Travelling salesman problem

More Related Videos

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

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

Published on: January 20, 2023

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

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

Published on: February 1, 2020

Related Experiment Videos

Last Updated: Feb 17, 2026

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Published on: July 24, 2021

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

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

Published on: January 20, 2023

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

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

Published on: February 1, 2020

Area of Science:

Operations Research
Combinatorial Optimization
Computer Science

Background:

The classical Traveling Salesman Problem (TSP) involves finding the shortest tour visiting each city once.
The q-stripe TSP extends TSP by considering costs to the next q cities in the tour.
This problem is a specific instance of the quadratic assignment problem.

Purpose of the Study:

To analyze the computational complexity of the q-stripe TSP.
To identify conditions under which the q-stripe TSP is NP-hard or polynomially solvable.
To generalize existing TSP theorems to the q-stripe TSP framework.

Main Methods:

Analysis of computational complexity for the q-stripe TSP.
Examination of specially structured distance matrices.
Derivation of NP-hardness results and identification of polynomially solvable cases.

Main Results:

The q-stripe TSP is shown to be NP-hard for certain classes of distance matrices.
Specific structures of distance matrices lead to polynomially solvable cases.
A key theorem by Kalmanson for the classical TSP is generalized to the q-stripe TSP.

Conclusions:

The computational complexity of the q-stripe TSP varies significantly based on the structure of the distance matrix.
The generalization of Kalmanson's theorem provides new insights into the q-stripe TSP.
This research contributes to understanding complex combinatorial optimization problems.