Copertina

Are Graph Neural Networks Optimal Approximation Algorithms?

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Yau, Morris, Karalias, Nikolaos, Lu, Eric, Xu, Jessica, Jegelka, Stefanie
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Machine Learning Artificial Intelligence Discrete Mathematics Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Approximation Algorithms for Optimal Hopsets
di: Dinitz, Michael, et al.
Pubblicazione: (2025)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
di: Wang, Chen, et al.
Pubblicazione: (2024)

Learning to Prune Instances of Steiner Tree Problem in Graphs
di: Zhang, Jiwei, et al.
Pubblicazione: (2022)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
di: Gahlawat, Harmender, et al.
Pubblicazione: (2025)

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
di: Weiss, Eyal, et al.
Pubblicazione: (2022)

An Approximation Algorithm for Monotone Submodular Cost Allocation
di: Mizutani, Ryuhei
Pubblicazione: (2025)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
di: Veldt, Nate, et al.
Pubblicazione: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
di: Mömke, Tobias, et al.
Pubblicazione: (2024)

Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP
di: Nanta, Jiratchaphat, et al.
Pubblicazione: (2025)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
di: Liang, Wei, et al.
Pubblicazione: (2024)

Tightest Admissible Shortest Path
di: Weiss, Eyal, et al.
Pubblicazione: (2023)

Computing and Learning on Combinatorial Data
di: Zhang, Simon
Pubblicazione: (2025)

Query Complexity of Tournament Solutions
di: Maiti, Arnab, et al.
Pubblicazione: (2016)

Optimal Enumeration of Eulerian Trails in Directed Graphs
di: Bals, Ben, et al.
Pubblicazione: (2026)

Optimal Padded Decomposition For Bounded Treewidth Graphs
di: Filtser, Arnold, et al.
Pubblicazione: (2024)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
di: Harada, Tsubasa, et al.
Pubblicazione: (2024)

Algorithmic Results for Weak Roman Domination Problem in Graphs
di: Paul, Kaustav, et al.
Pubblicazione: (2024)

Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracle
di: Baswana, Surender, et al.
Pubblicazione: (2023)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
di: Abbasi, Ali, et al.
Pubblicazione: (2026)

FO and MSO Model Checking on Temporal Graphs
di: Döring, Michelle, et al.
Pubblicazione: (2026)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
di: Efthymiou, Charilaos, et al.
Pubblicazione: (2023)

$σ$-Maximal Ancestral Graphs
di: Yao, Binghua, et al.
Pubblicazione: (2025)

Stable Approximation Algorithms for Dominating Set and Independent Set
di: de Berg, Mark, et al.
Pubblicazione: (2024)

A Tie-breaking based Local Search Algorithm for Stable Matching Problems
di: Qiu, Junyuan
Pubblicazione: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
di: Bourneuf, Romain, et al.
Pubblicazione: (2025)

Partial Optimality in the Preordering Problem
di: Stein, David, et al.
Pubblicazione: (2026)

Optimal hypersurface decision trees
di: He, Xi
Pubblicazione: (2025)

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

(Approximate) Matrix Multiplication via Convolutions
di: Uffenheimer, Yahel, et al.
Pubblicazione: (2025)

An Approximate Generalization of the Okamura-Seymour Theorem
di: Kumar, Nikhil
Pubblicazione: (2022)

Approximate Realizations for Outerplanaric Degree Sequences
di: Bar-Noy, Amotz, et al.
Pubblicazione: (2024)

Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
di: Tukan, Murad, et al.
Pubblicazione: (2024)

A Constant-Factor Approximation for Directed Latency
di: Blauth, Jannis, et al.
Pubblicazione: (2025)

Approximation algorithms for non-sequential star packing problems
di: Hu, Mengyuan, et al.
Pubblicazione: (2024)

Approximation of Spanning Tree Congestion using Hereditary Bisection
di: Kolman, Petr
Pubblicazione: (2024)

Approximately covering vertices by order-$5$ or longer paths
di: Gong, Mingyang, et al.
Pubblicazione: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
di: Davies, Sami, et al.
Pubblicazione: (2023)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
di: Disser, Yann, et al.
Pubblicazione: (2024)

Graph Inference with Effective Resistance Queries
di: Bennett, Huck, et al.
Pubblicazione: (2025)