Copertina

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Mao, Xiao
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

0-1 Knapsack in Nearly Quadratic Time
di: Jin, Ce
Pubblicazione: (2023)

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

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

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

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

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

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

Approximating Partition in Near-Linear Time
di: Chen, Lin, et al.
Pubblicazione: (2024)

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

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2023)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
di: Dughmi, Shaddin, et al.
Pubblicazione: (2025)

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

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

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

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
di: Mao, Xiao, et al.
Pubblicazione: (2026)

Approximate Counting for Spin Systems in Sub-Quadratic Time
di: Anand, Konrad, et al.
Pubblicazione: (2023)

Approximating Maximum Matching Requires Almost Quadratic Time
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
di: Adil, Deeksha, et al.
Pubblicazione: (2024)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

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

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
di: Bukov, Anton, et al.
Pubblicazione: (2023)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
di: Dai, Jiangqi, et al.
Pubblicazione: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
di: Solomon, Shay, et al.
Pubblicazione: (2023)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

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

Online Knapsack Problems with Estimates
di: Balabán, Jakub, 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)

A Nearly Quadratic Improvement for Memory Reallocation
di: Farach-Colton, Martin, et al.
Pubblicazione: (2024)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
di: Henzinger, Monika, et al.
Pubblicazione: (2025)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
di: Baligács, Júlia, et al.
Pubblicazione: (2024)

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

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
di: Bshouty, Nader H., et al.
Pubblicazione: (2026)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
di: Driemel, Anne, et al.
Pubblicazione: (2026)

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

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations
di: Kar, Debajyoti, et al.
Pubblicazione: (2026)

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

Fair Submodular Maximization over a Knapsack Constraint
di: Li, Lijun, et al.
Pubblicazione: (2025)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
di: Mao, Xiao
Pubblicazione: (2023)