Related Experiment Video
Updated: May 24, 2025
05:30
Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
472
A linear time algorithm for linearizing quadratic and higher-order shortest path problems
Eranda Çela1, Bettina Klinz1, Stefan Lendl2
1Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria.
Mathematical Programming
|March 3, 2025
Summary
Researchers developed a faster linear time algorithm for the Quadratic Shortest Path Problem (QSPP) on acyclic digraphs. This new method efficiently determines if a QSPP instance is linearizable, simplifying it to a classic Shortest Path Problem (SPP).
Area of Science:
- Discrete Mathematics
- Theoretical Computer Science
- Graph Theory
Background:
- The Quadratic Shortest Path Problem (QSPP) is an NP-hard problem.
- Linearizability of a QSPP instance means its equivalence to a classic Shortest Path Problem (SPP).
- The linearization problem for QSPP (LinQSPP) identifies linearizable instances and their corresponding SPP.
Purpose of the Study:
- To develop a novel, efficient algorithm for the LinQSPP on acyclic digraphs.
- To improve upon existing algorithms for solving the LinQSPP.
- To extend the findings to higher-order shortest path problems.
Main Methods:
- A new linear time algorithm for LinQSPP on acyclic digraphs.
- Leveraging a novel insight that linearizability is a local property for acyclic digraphs.
- Algorithm design based on graph traversal and local property analysis.
Main Results:
- A linear time algorithm for LinQSPP on acyclic digraphs, outperforming previous methods.
- Demonstration that QSPP linearizability on acyclic digraphs is a local property.
- The approach is extendable to higher-order shortest path problems.
Conclusions:
- A significantly faster algorithm for LinQSPP on acyclic digraphs has been developed.
- The local property insight simplifies the analysis and solution of QSPP linearization.
- The presented method offers a more efficient approach to a class of shortest path problems.
Related Concept Videos
01:21Linear Approximation in Time Domain
59
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
59
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
38
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
38
01:23Linear time-invariant Systems
202
A system is linear if it displays the characteristics of homogeneity and additivity, together termed the superposition property. This principle is fundamental in all linear systems. Linear time-invariant (LTI) systems include systems with linear elements and constant parameters.
The input-output behavior of an LTI system can be fully defined by its response to an impulsive excitation at its input. Once this impulse response is known, the system's reaction to any other input can be...
The input-output behavior of an LTI system can be fully defined by its response to an impulsive excitation at its input. Once this impulse response is known, the system's reaction to any other input can be...
202
01:17Kinematic Equations - II
9.2K
The second kinematic equation expresses the final position of an object in terms of its initial position, the distance traveled with the initial constant velocity, and the distance traveled due to a change in velocity. Similar to the first kinematic equation, this equation is also only valid when the acceleration is constant throughout the motion of an object.
Suppose a car merges into freeway traffic on a 200 m long ramp. If its initial velocity is 10 m/s and it accelerates at 2 m/s2, then the...
Suppose a car merges into freeway traffic on a 200 m long ramp. If its initial velocity is 10 m/s and it accelerates at 2 m/s2, then the...
9.2K
01:15Kinematic Equations: Problem Solving
11.8K
When analyzing one-dimensional motion with constant acceleration, the problem-solving strategy involves identifying the known quantities and choosing the appropriate kinematic equations to solve for the unknowns. Either one or two kinematic equations are needed to solve for the unknowns, depending on the known and unknown quantities. Generally, the number of equations required is the same as the number of unknown quantities in the given example. Two-body pursuit problems always require two...
11.8K
01:26Linear Approximation in Frequency Domain
84
Linear systems are characterized by two main properties: superposition and homogeneity. Superposition allows the response to multiple inputs to be the sum of the responses to each individual input. Homogeneity ensures that scaling an input by a scalar results in the response being scaled by the same scalar.
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
In contrast, nonlinear systems do not inherently possess these properties. However, for small deviations around an operating point, a nonlinear system can often be approximated as linear....
84