Copertina

Fine Grained Lower Bounds for Multidimensional Knapsack

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Doron-Arad, Ilan, Kulik, Ariel, Manurangsi, Pasin
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
di: Doron-Arad, Ilan, et al.
Pubblicazione: (2023)

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

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

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

Improved Lower Bound for Differentially Private Facility Location
di: Manurangsi, Pasin
Pubblicazione: (2024)

Non-Linear Paging
di: Doron-Arad, Ilan, et al.
Pubblicazione: (2024)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
di: Manurangsi, Pasin
Pubblicazione: (2024)

Improved Approximation Algorithm for Maximum Balanced Biclique
di: Manurangsi, Pasin
Pubblicazione: (2026)

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
di: Epasto, Alessandro, et al.
Pubblicazione: (2026)

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

Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High $\varepsilon$ Regime
di: Harrison, Charlie, et al.
Pubblicazione: (2025)

Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms
di: Harrison, Charlie, et al.
Pubblicazione: (2025)

Nearly-Optimal Private Selection via Gaussian Mechanism
di: Leeman, Ethan, et al.
Pubblicazione: (2025)

Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
di: Chua, Lynn, et al.
Pubblicazione: (2026)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
di: S., Karthik C., et al.
Pubblicazione: (2024)

A Note on Approximability of Densest At-Least-k-Subgraph
di: Laekhanukit, Bundit, et al.
Pubblicazione: (2026)

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

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

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

Improved Differentially Private Algorithms for Rank Aggregation
di: Hillebrand, Quentin, et al.
Pubblicazione: (2025)

Algorithmic Persuasion with Evidence
di: Hoefer, Martin, et al.
Pubblicazione: (2020)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
di: Hao, Yimin, et al.
Pubblicazione: (2025)

Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
di: Ghazi, Badih, et al.
Pubblicazione: (2024)

On Computing Pairwise Statistics with Local Differential Privacy
di: Ghazi, Badih, et al.
Pubblicazione: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

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

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

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

Linear-Time User-Level DP-SCO via Robust Statistics
di: Ghazi, Badih, et al.
Pubblicazione: (2025)

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

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

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

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

Private Hyperparameter Tuning with Ex-Post Guarantee
di: Ghazi, Badih, et al.
Pubblicazione: (2025)

The Price of Privacy For Approximating Max-CSP
di: Dharangutte, Prathamesh, et al.
Pubblicazione: (2026)

Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity
di: Regehr, Matthew, et al.
Pubblicazione: (2026)

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

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

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

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