Cover Image

Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Sim, Chee-Khian
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
by: Ketkov, Sergey S., et al.
Published: (2024)

First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex
by: Sim, Chee-Khian
Published: (2025)

Superlinear Convergence of an Interior Point Algorithm on Linear Semi-definite Feasibility Problems
by: Sim, Chee-Khian
Published: (2022)

On the Induced Norms of Matrices and Grothendieck problems
by: Truong, Lan V., et al.
Published: (2026)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
by: Prunet, Thibault, et al.
Published: (2023)

Hardness of some optimization problems over correlation polyhedra
by: Caprara, Alberto, et al.
Published: (2026)

Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is $o(ε^{-2})$ rather than $\mathcal{O}(ε^{-2})$
by: Gratton, Serge, et al.
Published: (2024)

Information Redistribution Under Reductions in NP Search
by: Wei, Jing-Yuan
Published: (2026)

Learning complexity of gradient descent and conjugate gradient algorithms
by: Jiao, Xianqi, et al.
Published: (2024)

Parameterized complexity of scheduling unit-time jobs with generalized precedence constraints
by: Büsing, Christina, et al.
Published: (2025)

A System-Dynamic Based Simulation and Bayesian Optimization for Inventory Management
by: Maitra, Sarit
Published: (2024)

Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
by: Tyurin, Alexander
Published: (2024)

Benchmarking of Quantum and Classical Computing in Large-Scale Dynamic Portfolio Optimization Under Market Frictions
by: Chen, Ying, et al.
Published: (2025)

Semidefinite programming and linear equations vs. homomorphism problems
by: Ciardo, Lorenzo, et al.
Published: (2023)

Avoiding Deadlocks via Weak Deadlock Sets
by: Oriolo, Gianpaolo, et al.
Published: (2024)

Geometric and computational hardness of bilevel programming
by: Bolte, Jérôme, et al.
Published: (2024)

A parallel framework for graphical optimal transport
by: Fan, Jiaojiao, et al.
Published: (2024)

On the Complexity of p-Order Cone Programs
by: Blanco, Víctor, et al.
Published: (2025)

Efficient LP warmstarting for linear modifications of the constraint matrix
by: Derval, Guillaume, et al.
Published: (2025)

Constrained Nonnegative Gram Feasibility is $\exists\mathbb{R}$-Complete
by: Majumdar, Angshul
Published: (2026)

On the Degree Automatability of Sum-of-Squares Proofs
by: Bortolotti, Alex, et al.
Published: (2025)

Counterfactual Explanations for Integer Optimization Problems
by: Engelhardt, Felix, et al.
Published: (2025)

Policy Gradient Algorithms in Average-Reward Multichain MDPs
by: Lee, Jongmin, et al.
Published: (2026)

A parameterized linear formulation of the integer hull
by: Eisenbrand, Friedrich, et al.
Published: (2025)

The Complexity of Computing KKT Solutions of Quadratic Programs
by: Fearnley, John, et al.
Published: (2023)

Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees
by: Boche, Holger, et al.
Published: (2025)

On Big-M Reformulations of Bilevel Linear Programs: Hardness of A Posteriori Verification
by: Ketkov, Sergey S., et al.
Published: (2026)

The Complexity of Recognizing Facets for the Knapsack Polytope
by: Chen, Rui, et al.
Published: (2022)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms
by: Bhargav, Jayanth, et al.
Published: (2024)

Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization
by: Jin, Ruiyang, et al.
Published: (2025)

On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
by: Diaby, Moustapha, et al.
Published: (2023)

A graph-based algorithm for the non-stationary lot-sizing problem with penalty scheme
by: Ma, Xiyuan, et al.
Published: (2024)

Real Stability and Log Concavity are coNP-Hard
by: Chin, Tracy
Published: (2024)

Accelerating genetic optimization of nonlinear model predictive control by learning optimal search space size
by: Mostafa, Eslam, et al.
Published: (2023)

Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
by: Borzechowski, Michaela, et al.
Published: (2024)

A matheuristic approach for an integrated lot-sizing and scheduling problem with a period-based learning effect
by: Rohaninejad, Mohammad, et al.
Published: (2024)

Solving The Travelling Salesman Problem Using A Single Qubit
by: Goswami, Kapil, et al.
Published: (2024)

Linear Equations with Min and Max Operators: Computational Complexity
by: Chatterjee, Krishnendu, et al.
Published: (2024)

From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
by: Pedramfar, Mohammad, et al.
Published: (2024)