Cover Image

Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lev-Ran, Asaf, Arkhipov, Pavel, Kolmogorov, Vladimir
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
by: Arkhipov, Pavel, et al.
Published: (2026)

Faster algorithms for packing forests in graphs and related problems
by: Arkhipov, Pavel, et al.
Published: (2024)

Greedy matroid base packings with applications to dynamic graph density and orientations
by: Arkhipov, Pavel, et al.
Published: (2025)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

A computational study of Gomory-Hu construction tree algorithms
by: Kolmogorov, Vladimir
Published: (2022)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

OrderedCuts: A new approach for computing Gomory-Hu tree
by: Kolmogorov, Vladimir
Published: (2022)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

Simple parallel estimation of the partition ratio for Gibbs distributions
by: Harris, David G., et al.
Published: (2025)

A new notion of commutativity for the algorithmic Lovász Local Lemma
by: Harris, David G., et al.
Published: (2020)

VertiMRF: Differentially Private Vertical Federated Data Synthesis
by: Zhao, Fangyuan, et al.
Published: (2024)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
by: Chen, Tianqi, et al.
Published: (2025)

Fault-Equivalent Lowest Common Ancestors
by: Petruschka, Asaf
Published: (2024)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
by: Zhao, Zhuowei, et al.
Published: (2025)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
by: Cervenjak, Philip, et al.
Published: (2024)

Parameter estimation for Gibbs distributions
by: Harris, David G., et al.
Published: (2020)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
by: Parter, Merav, et al.
Published: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
by: Bhanja, Koustav, et al.
Published: (2025)

Connectivity Labeling in Faulty Colored Graphs
by: Petruschka, Asaf, et al.
Published: (2024)

New Oracles and Labeling Schemes for Vertex Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
by: Ferber, Asaf, et al.
Published: (2025)

Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
by: Henzinger, Monika, et al.
Published: (2024)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
by: Zhao, Jingyang, et al.
Published: (2025)

On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
by: Blažej, Václav, et al.
Published: (2024)

Polynomial Property Testing
by: Gishboliner, Lior, et al.
Published: (2025)

Relative Error Streaming Quantiles with Seamless Mergeability via Adaptive Compactors
by: Domes, Tomáš, et al.
Published: (2025)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
by: Parter, Merav, et al.
Published: (2024)

An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
by: Bai, Tian
Published: (2025)

FLASH-TB: Integrating Arc-Flags and Trip-Based Public Transit Routing
by: Großmann, Ernestine, et al.
Published: (2023)

Paralleling and Accelerating Arc Consistency Enforcement with Recurrent Tensor Computations
by: Yang, Mingqi
Published: (2024)

Competitively Consistent Clustering
by: Buchbinder, Niv, et al.
Published: (2025)

Consistent Low-Rank Approximation
by: Woodruff, David P., et al.
Published: (2026)

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
by: Banik, Aritra, et al.
Published: (2025)

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
by: Con, Roni, et al.
Published: (2024)

Beyond Worst Case Local Computation Algorithms
by: Biswas, Amartya Shankha, et al.
Published: (2024)

Counting Unit Circular Arc Intersections
by: Wang, Haitao
Published: (2026)

Faster optimal univariate microgaggregation
by: Stamm, Felix I., et al.
Published: (2024)

Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting
by: Jeang, John, et al.
Published: (2026)

Interactive Coding with Unbounded Noise
by: Fargion, Eden, et al.
Published: (2024)