Cover Image

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kurpisz, Adam, Slot, Lucas, Zaytsev, Mikhail
Format:	Preprint
Published:	2026
Subjects:	Optimization and Control Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
by: Chen, Shengminjie, et al.
Published: (2026)

A Control-Theoretic Perspective on Optimal High-Order Optimization
by: Lin, Tianyi, et al.
Published: (2019)

A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
by: Lin, Tianyi, et al.
Published: (2022)

Solving convex QPs with structured sparsity under indicator conditions
by: Bienstock, Daniel, et al.
Published: (2024)

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

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

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
by: Gribanov, Dmitry, et al.
Published: (2026)

Unifying Formal Explanations: A Complexity-Theoretic Perspective
by: Bassan, Shahaf, et al.
Published: (2026)

Simultaneous Network Design with Restricted Link Usage
by: Kakimura, Naonori, et al.
Published: (2025)

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

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
by: Cherniavskii, M., et al.
Published: (2024)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
by: Blanchard, Moise
Published: (2024)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
by: Kunisky, Dmitriy, et al.
Published: (2022)

Efficient Convex Optimization Requires Superlinear Memory
by: Marsden, Annie, et al.
Published: (2022)

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

Removable Online Knapsack and Advice
by: Böckenhauer, Hans-Joachim, et al.
Published: (2020)

Knapsack on Graphs with Relaxed Neighborhood Constraints
by: Dey, Palash, et al.
Published: (2025)

Generalized Assignment and Knapsack Problems in the Random-Order Model
by: Klimm, Max, et al.
Published: (2025)

Efficient approximation schemes for scheduling on a stochastic number of machines
by: Epstein, Leah, et al.
Published: (2024)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
by: Diaby, Moustapha
Published: (2016)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
by: Singh, Sipra
Published: (2025)

Cascading-Tree Algorithm for the 0-1 Knapsack Problem (In Memory of Heiner M{ü}ller-Merbach, a Former President of IFORS)
by: Moeini, Mahdi, et al.
Published: (2024)

Minimum Stable Cut and Treewidth
by: Lampis, Michael
Published: (2021)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Equivalent Instances for Scheduling and Packing Problems
by: Jansen, Klaus, et al.
Published: (2025)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
by: Upirvitskiy, Aleksey, et al.
Published: (2026)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
by: Bilò, Davide, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
by: Schade, Jamico, et al.
Published: (2023)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
by: Stoian, Mihail
Published: (2024)

Min-Max Optimization Requires Exponentially Many Queries
by: Bernasconi, Martino, et al.
Published: (2026)

Asymptotic Rank Speedup Theorems, Revisited
by: Alman, Josh, et al.
Published: (2026)

Improved Approximation Guarantees and Hardness Results for MNL-Driven Product Ranking
by: Segev, Danny, et al.
Published: (2025)

Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Near-Optimality for Single-Source Personalized PageRank
by: Jiang, Xinpeng, et al.
Published: (2025)

Computational complexity of the recoverable robust shortest path problem in acyclic digraphs
by: Kasperski, Adam, et al.
Published: (2024)

Distributionally Robust Newsvendor on a Metric
by: Foussoul, Ayoub, et al.
Published: (2024)