Copertina

Approximating Partition in Near-Linear Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chen, Lin, Lian, Jiayi, Mao, Yuchen, Zhang, Guochuan
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

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

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

A Note on Deterministic FPTAS for Partition
di: Chen, Lin, et al.
Pubblicazione: (2025)

An Improved Pseudopolynomial Time Algorithm for Subset Sum
di: Chen, Lin, et al.
Pubblicazione: (2024)

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

Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
di: Chen, Lin, et al.
Pubblicazione: (2025)

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

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

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

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

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
di: Harada, Kaito, et al.
Pubblicazione: (2024)

Vizing's Theorem in Near-Linear Time
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
di: Agarwal, Arpit, et al.
Pubblicazione: (2024)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
di: Gottesbüren, Lars, et al.
Pubblicazione: (2025)

LinearPartition: Linear-Time Approximation of RNA Folding Partition Function and Base Pairing Probabilities
di: Zhang, He, et al.
Pubblicazione: (2019)

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

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

Approximating Directed Connectivity in Almost-Linear Time
di: Quanrud, Kent
Pubblicazione: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
di: Koh, Zhuan Khye, et al.
Pubblicazione: (2024)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
di: Fischer, Nick, et al.
Pubblicazione: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
di: Henzinger, Monika, et al.
Pubblicazione: (2024)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
di: Boneh, Itai, et al.
Pubblicazione: (2025)

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

Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time
di: Objois, Étienne, et al.
Pubblicazione: (2025)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
di: Terao, Tatsuya
Pubblicazione: (2024)

Fully Subexponential Time Approximation Scheme for Product Partition
di: Costandin, Marius
Pubblicazione: (2024)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
di: Elkin, Michael, et al.
Pubblicazione: (2024)

Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
di: Gavva, Surya Teja, et al.
Pubblicazione: (2025)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
di: Dhawan, Abhishek
Pubblicazione: (2024)

Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
di: Hellerstein, Lisa, et al.
Pubblicazione: (2026)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
di: Mömke, Tobias, et al.
Pubblicazione: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
di: Hua, Kevin, et al.
Pubblicazione: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Parameterized Approximability for Modular Linear Equations
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2025)

Faster Approximate Linear Matroid Intersection
di: Terao, Tatsuya
Pubblicazione: (2026)

Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor
di: Aliakbarpour, Maryam, et al.
Pubblicazione: (2025)

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
di: Choromanski, Krzysztof, et al.
Pubblicazione: (2026)

Optimal FPT-Approximability for Modular Linear Equations
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2026)

Ortho-Radial Drawing in Near-Linear Time
di: Chang, Yi-Jun
Pubblicazione: (2023)

Approximating Submodular Matroid-Constrained Partitioning
di: Bérczi, Kristóf, et al.
Pubblicazione: (2025)