Buchumschlag

An approximation algorithm for Maximum DiCut vs. Cut

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Nakajima, Tamio-Vesa, Živný, Stanislav
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Discrete Mathematics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Maximum $k$- vs. $\ell$-colourings of graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2023)

A Dichotomy for Maximum PCSPs on Graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

On the complexity of symmetric vs. functional PCSPs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2022)

A logarithmic approximation of linearly ordered colourings
von: Håstad, Johan, et al.
Veröffentlicht: (2024)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
von: Bedert, Benjamin, et al.
Veröffentlicht: (2025)

Maximum And- vs. Even-SAT
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Additive Sparsification of CSPs
von: Pelleg, Eden, et al.
Veröffentlicht: (2021)

Semidefinite programming and linear equations vs. homomorphism problems
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

The periodic structure of local consistency
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2024)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
von: Shao, Shuai, et al.
Veröffentlicht: (2023)

On the Bidirected Cut Relaxation for Steiner Forest
von: Byrka, Jarosław, et al.
Veröffentlicht: (2024)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Cuts in Graphs with Matroid Constraints
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Cuts and Gauges for Submodular Width
von: Lanzinger, Matthias
Veröffentlicht: (2026)

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
von: Byrka, Jarosław, et al.
Veröffentlicht: (2024)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
von: Johnson, Matthew, et al.
Veröffentlicht: (2022)

EPTAS for Hard Graph Cut Problems for Dense Graphs
von: Deguchi, Kaisei, et al.
Veröffentlicht: (2026)

Thin Trees via $k$-Respecting Cut Identities
von: Daga, Mohit
Veröffentlicht: (2025)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
von: Arndt, Stephen, et al.
Veröffentlicht: (2026)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
von: Lucke, Felicia, et al.
Veröffentlicht: (2023)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
von: Chen, Yu, et al.
Veröffentlicht: (2023)

Fast approximation algorithms for the 1-median problem on real-world large graphs
von: Ueta, Keisuke, et al.
Veröffentlicht: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
von: Lill, Jonas, et al.
Veröffentlicht: (2024)

New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
von: Prasad, Siddharth, et al.
Veröffentlicht: (2024)

Deterministic Minimum Steiner Cut in Maximum Flow Time
von: Ding, Matthew, et al.
Veröffentlicht: (2023)

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

Finding $d$-Cuts in Probe $H$-Free Graphs
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2025)

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

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

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
von: Kratochvíl, Jan, et al.
Veröffentlicht: (2020)

Approximation algorithms for non-sequential star packing problems
von: Hu, Mengyuan, et al.
Veröffentlicht: (2024)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
von: Veldt, Nate
Veröffentlicht: (2025)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
von: de Montgolfier, Fabien, et al.
Veröffentlicht: (2025)

A 4-approximation algorithm for min max correlation clustering
von: Heidrich, Holger, et al.
Veröffentlicht: (2023)

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
von: Tan, Jingjing
Veröffentlicht: (2024)

Solving the List Coloring Problem through a Branch-and-Price algorithm
von: Lucci, Mauro, et al.
Veröffentlicht: (2023)

A column generation algorithm for finding co-3-plexes in chordal graphs
von: Dupont-Bouillard, Alexandre
Veröffentlicht: (2026)