Cover Image

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Doron-Arad, Ilan, Kulik, Ariel, Shachnai, Hadas
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
by: Doron-Arad, Ilan, et al.
Published: (2023)

You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
by: Doron-Arad, Ilan, et al.
Published: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
by: Doron-Arad, Ilan, et al.
Published: (2024)

Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
by: Kulik, Ariel, et al.
Published: (2019)

Unsplittable Flow on a Short Path
by: Doron-Arad, Ilan, et al.
Published: (2024)

Approximations and Hardness of Packing Partially Ordered Items
by: Doron-Arad, Ilan, et al.
Published: (2024)

An Algorithm-to-Contract Framework without Demand Queries
by: Doron-Arad, Ilan, et al.
Published: (2025)

Non-Linear Paging
by: Doron-Arad, Ilan, et al.
Published: (2024)

$k$-Clustering via Iterative Randomized Rounding
by: Byrka, Jarosław, et al.
Published: (2026)

Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities
by: Bai, Miao, et al.
Published: (2023)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
by: Esmer, Barış Can, et al.
Published: (2024)

EPTAS for Hard Graph Cut Problems for Dense Graphs
by: Deguchi, Kaisei, et al.
Published: (2026)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

Proportionally Fair Matching via Randomized Rounding
by: Duppala, Sharmila, et al.
Published: (2024)

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

Randomized Rounding over Dynamic Programs
by: Bamas, Etienne, et al.
Published: (2025)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
by: Friggstad, Zachary, et al.
Published: (2025)

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

A Poisson Process for Submodular Maximization
by: Rozenman, Amit Ganz, et al.
Published: (2026)

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

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)

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

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
by: Ma, Will
Published: (2024)

A Randomized Rounding Approach for DAG Edge Deletion
by: Kalantarzadeh, Sina, et al.
Published: (2025)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
by: Rohwedder, Lars, et al.
Published: (2025)

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)

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

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
by: Li, Shi
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)

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)

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

On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms
by: Schlöter, Jens
Published: (2025)

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