Cover Image

Formal Primal-Dual Algorithm Analysis

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abdulaziz, Mohammad, Ammer, Thomas, Madlener, Christoph
Format:	Preprint
Published:	2026
Subjects:	Logic in Computer Science Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Iteration Number of the Weisfeiler-Leman Algorithm
by: Grohe, Martin, et al.
Published: (2023)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
by: Lyon, Tim S., et al.
Published: (2023)

Color Refinement for Relational Structures
by: Scheidt, Benjamin, et al.
Published: (2024)

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

On classes of bounded tree rank, their interpretations, and efficient sparsification
by: Gajarský, Jakub, et al.
Published: (2024)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
by: Koh, Zhuan Khye, et al.
Published: (2021)

Solving Partial Dominating Set and Related Problems Using Twin-Width
by: Balabán, Jakub, et al.
Published: (2025)

SDPs and Robust Satisfiability of Promise CSP
by: Brakensiek, Joshua, et al.
Published: (2022)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

Merge-width and First-Order Model Checking
by: Dreier, Jan, et al.
Published: (2025)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by: Faber, Daniel, et al.
Published: (2024)

Redundancy Is All You Need (for CSP Sparsification)
by: Brakensiek, Joshua, et al.
Published: (2024)

Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
by: Kevi, Eniko, et al.
Published: (2024)

A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
by: Proença, Nathan Benedetto, et al.
Published: (2023)

Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
by: Proença, Nathan Benedetto, et al.
Published: (2024)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Algorithmic Aspects of Temporal Betweenness
by: Buß, Sebastian, et al.
Published: (2020)

From Width-Based Model Checking to Width-Based Automated Theorem Proving
by: Oliveira, Mateus de Oliveira, et al.
Published: (2022)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Terminal Steiner tree problem : Complexity and Algorithms
by: S, Jyothish, et al.
Published: (2026)

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

Matching Algorithms in the Sparse Stochastic Block Model
by: Brandenberger, Anna, et al.
Published: (2024)

Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac
by: Ingels, Florian
Published: (2023)

Improved Streaming Algorithm for Fair $k$-Center Clustering
by: Guo, Longkun, et al.
Published: (2025)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
by: Madathil, Jayakrishnan, et al.
Published: (2024)

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

Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms
by: Ekbatani, Farbod, et al.
Published: (2026)

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

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

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