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

Application of Nonlinear Inequalities01:29

Application of Nonlinear Inequalities

357
A nonlinear inequality describes a comparison involving an expression that curves or behaves more complexly than a straight line. These inequalities often appear in forms that include squares, products, or variables in the denominator.To solve such an inequality, one starts by rewriting it so that zero appears on one side. For example, the inequality:  can be factored as: This form makes it easier to identify the values that cause the expression to equal zero. In this case, the...
357
Introduction to Nonlinear Inequalities01:25

Introduction to Nonlinear Inequalities

326
Linear and nonlinear inequalities are fundamental for analyzing variable relationships and identifying ranges satisfying specific conditions. A linear inequality involves variables raised only to the first power, resulting in a straight-line graph. This line partitions the coordinate plane into two distinct regions: one that satisfies the inequality and one that does not. Each region represents a set of solutions where the linear relationship holds true under the specified constraint.Nonlinear...
326
Block Diagram Reduction01:22

Block Diagram Reduction

727
The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
727
The Squeeze Theorem01:30

The Squeeze Theorem

453
Certain mathematical functions exhibit unpredictable or highly variable behavior near specific input values, making direct evaluation of their limits challenging. This complexity may arise from rapid oscillations or irregular patterns that obscure the function’s trend. In such cases, the Squeeze Theorem offers a reliable method for determining limits.According to the Squeeze Theorem, if a function is confined between two other functions near a particular point, and both outer functions...
453
Statically Indeterminate Problem Solving01:16

Statically Indeterminate Problem Solving

948
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...
948
Graphical Representation of Inequalities01:28

Graphical Representation of Inequalities

451
The graph of the equation where y equals x squared forms a curve known as a parabola. This curve acts as a boundary in the coordinate plane, dividing it into distinct regions based on the relative position of points.When the equality sign in the equation is replaced with an inequality—such as greater than, less than, greater than or equal to, or less than or equal to—the graphical representation changes from a single curve into a broader shaded area that signifies the set of all...
451

You might also read

Related Articles

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

Sort by
Same author

Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming.

Mathematical programming·2024
Same author

About the complexity of two-stage stochastic IPs.

Mathematical programming·2022
Same author

Inhibition of nucleotide pyrophosphatase/phosphodiesterase 1: implications for developing a calcium pyrophosphate deposition disease modifying drug.

Rheumatology (Oxford, England)·2018
Same journal

A better-than-1.6-approximation for prize-collecting TSP.

Mathematical programming·2026
Same journal

A <math><mrow><mfrac><mn>4</mn> <mn>3</mn></mfrac></mrow></math> -approximation for the maximum leaf spanning arborescence problem in DAGs.

Mathematical programming·2026
Same journal

An FPTAS for Connectivity Interdiction.

Mathematical programming·2026
Same journal

A first order method for linear programming parameterized by circuit imbalance.

Mathematical programming·2026
Same journal

Accelerated first-order optimization under nonlinear constraints.

Mathematical programming·2026
Same journal

Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices.

Mathematical programming·2025
See all related articles

Related Experiment Video

Updated: May 2, 2026

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules
10:58

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules

Published on: July 25, 2013

16.2K

Tight lower bounds for block-structured integer programs.

Christoph Hunkenschröder1, Kim-Manuel Klein2, Martin Koutecký3

  • 1(Formerly) Institut für Mathematik, TU Berlin, Berlin, Germany.

Mathematical Programming
|May 1, 2026
PubMed
Summary
This summary is machine-generated.

We prove that the exponential time gap in solving tree-fold and multi-stage integer programs (IPs) is inherent, showing current algorithms are nearly optimal. Unconditional lower bounds on Graver basis elements also limit improvements for these fundamental IPs.

Keywords:
(Unconditional) lower boundsETHInteger programmingMulti-stage IPsSubset sumTree-fold IPsn-fold IPs

Related Experiment Videos

Last Updated: May 2, 2026

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules
10:58

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules

Published on: July 25, 2013

16.2K

Area of Science:

  • Theoretical Computer Science
  • Operations Research
  • Discrete Mathematics

Background:

  • Studies fundamental block-structured integer programs (IPs): tree-fold and multi-stage IPs.
  • These IPs exhibit a recursive pattern in their constraint matrices, with tree-fold IPs being transposes of multi-stage IPs.
  • Current algorithms for solving these IPs possess a significant exponential time gap.

Purpose of the Study:

  • To determine if the exponential time gap in solving tree-fold and multi-stage IPs is inherent.
  • To establish theoretical limits on the efficiency of algorithms for these specific IP structures.
  • To investigate the fundamental building blocks of existing algorithms, such as Graver basis elements.

Main Methods:

  • Proving lower bounds based on the Exponential Time Hypothesis (ETH).
  • Analyzing the structure of constraint matrices for tree-fold and multi-stage IPs.
  • Establishing unconditional lower bounds on the size of Graver basis elements.

Main Results:

  • Demonstrated that the exponential time gap in solving these IPs is necessary, assuming the ETH.
  • Established that current state-of-the-art algorithms are essentially optimal in terms of their exponential running time.
  • Proved unconditional lower bounds on the size of Graver basis elements, indicating limitations for current algorithmic approaches.

Conclusions:

  • The exponential time complexity for solving tree-fold and multi-stage integer programs is inherent and cannot be fundamentally improved.
  • Existing algorithms are close to optimal, and significant breakthroughs in polynomial time are unlikely under standard complexity assumptions.
  • Future improvements to algorithms solving these IPs are constrained by the established lower bounds on Graver basis elements.