Cover Image

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dughmi, Shaddin, Kalayci, Yusuf Hakan, Liu, Xinyu
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Limitations of Stochastic Selection with Pairwise Independent Priors
by: Dughmi, Shaddin, et al.
Published: (2023)

Is Transductive Learning Equivalent to PAC Learning?
by: Dughmi, Shaddin, et al.
Published: (2024)

PAC Learning is just Bipartite Matching (Sort of)
by: Dughmi, Shaddin
Published: (2025)

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

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
by: Buchem, Moritz, et al.
Published: (2024)

Improved Tree Sparsifiers in Near-Linear Time
by: Agassy, Daniel, et al.
Published: (2025)

Online Knapsack Problems with Estimates
by: Balabán, Jakub, et al.
Published: (2025)

Average sensitivity of the Knapsack Problem
by: Kumabe, Soh, et al.
Published: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
by: Das, Syamantak, et al.
Published: (2024)

0-1 Knapsack in Nearly Quadratic Time
by: Jin, Ce
Published: (2023)

A Nearly Quadratic-Time FPTAS for Knapsack
by: Chen, Lin, et al.
Published: (2023)

Knapsack with Small Items in Near-Quadratic Time
by: Bringmann, Karl
Published: (2023)

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
by: Mao, Xiao
Published: (2023)

Stochastic Knapsack: Semi-Adaptivity Gaps and Improved Approximation
by: Barak, Zohar, et al.
Published: (2026)

Sparsifying Sums of Positive Semidefinite Matrices
by: Basu, Arpon, et al.
Published: (2025)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

Nearly Optimal Bounds for Stochastic Online Sorting
by: Hu, Yang
Published: (2025)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
by: Ma, Will, et al.
Published: (2019)

Online Unbounded Knapsack
by: Böckenhauer, Hans-Joachim, et al.
Published: (2024)

The Online Submodular Assignment Problem
by: Hathcock, Daniel, et al.
Published: (2024)

The Online Submodular Assignment Problem
by: Hathcock, Daniel, et al.
Published: (2024)

An Exact Solver for Submodular Knapsack Problems
by: Münch, Sabine, et al.
Published: (2025)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

A Near-Optimal Kernel for a Coloring Problem
by: Haviv, Ishay, et al.
Published: (2025)

Transductive Learning Is Compact
by: Asilis, Julian, et al.
Published: (2024)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Convolution and Knapsack in Higher Dimensions
by: Grage, Kilian, et al.
Published: (2024)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
by: Zhao, Yibin
Published: (2025)

Sparsifying Cayley Graphs on Every Group
by: Hsieh, Jun-Ting, et al.
Published: (2025)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
by: Chen, Yu, et al.
Published: (2024)

Online General Knapsack with Reservation Costs
by: Burjons, Elisabet, et al.
Published: (2025)

Weakly Approximating Knapsack in Subquadratic Time
by: Chen, Lin, et al.
Published: (2025)

Twice-Ramanujan Sparsifiers
by: Batson, Joshua, et al.
Published: (2008)

Many Hamiltonians Are Sparsifiable
by: Basu, Arpon, et al.
Published: (2026)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
by: Paschalidis, Phevos, et al.
Published: (2023)

Performance of the Extended Ising Machine for the Quadratic Knapsack Problem
by: Akishima, Haruka, et al.
Published: (2025)

Improved Approximation Algorithms for Three-Dimensional Knapsack
by: Jansen, Klaus, et al.
Published: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)