Imagen de Portada

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Choromanski, Krzysztof, Long, Derek, Parashar, Ananya, Saha, Dwaipayan
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms Methodology
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs
por: Wienöbst, Marcel, et al.
Publicado: (2022)

Graph Generation Methods under Partial Information
por: Sun, Tong, et al.
Publicado: (2026)

Linear-Time Primitives for Algorithm Development in Graphical Causal Inference
por: Wienöbst, Marcel, et al.
Publicado: (2025)

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

An efficient heuristic for approximate maximum flow computations
por: Qian, Jingyun, et al.
Publicado: (2024)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
por: Duraj, Lech, et al.
Publicado: (2023)

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

Dynamic PageRank: Algorithms and Lower Bounds
por: Jayaram, Rajesh, et al.
Publicado: (2024)

The Conflict Graph Design: Estimating Causal Effects under Arbitrary Neighborhood Interference
por: Kandiros, Vardis, et al.
Publicado: (2024)

A Near-Real-Time Reduction-Based Algorithm for Coloring Massive Graphs
por: Zhu, Chenghao, et al.
Publicado: (2025)

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

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

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
por: Jiang, Shunhua, et al.
Publicado: (2025)

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

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
por: Alejandro-Soto, J. A., et al.
Publicado: (2025)

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

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

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
por: Feldmann, Andreas Emil, et al.
Publicado: (2024)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
por: Brand, Jan van den, et al.
Publicado: (2024)

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

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

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

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Importance Sparsification for Sinkhorn Algorithm
por: Li, Mengyu, et al.
Publicado: (2023)

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

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

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
por: Geng, Yutong, et al.
Publicado: (2025)

Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size
por: Chanda, Debarshi
Publicado: (2025)

Bellman-Ford in Almost-Linear Time for Dense Graphs
por: Li, George Z., et al.
Publicado: (2026)

Separator Theorem for Minor-Free Graphs in Linear Time
por: Bonnet, Édouard, et al.
Publicado: (2025)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
por: Fischer, Nick, et al.
Publicado: (2024)

Unbreakable Decomposition in Close-to-Linear Time
por: Anand, Aditya, et al.
Publicado: (2024)

A Statistical View of Column Subset Selection
por: Sood, Anav, et al.
Publicado: (2023)

Spike-and-Slab Posterior Sampling in High Dimensions
por: Kumar, Syamantak, et al.
Publicado: (2025)

Recursive Modified Pattern Search on High-dimensional Simplex : A Blackbox Optimization Technique
por: Das, Priyam
Publicado: (2016)

Causal Discovery under Off-Target Interventions
por: Choo, Davin, et al.
Publicado: (2024)

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

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

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

A Lower Bound for Light Spanners in General Graphs
por: Bodwin, Greg, et al.
Publicado: (2024)