Image de couverture de livre

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Michel, Lukas, Scott, Alex
Format:	Preprint
Publié:	2023
Sujets:	Data Structures and Algorithms Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Max-Cut with $ε$-Accurate Predictions
par: Cohen-Addad, Vincent, et autres
Publié: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
par: Fei, Yumou, et autres
Publié: (2025)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
par: Huang, Jeremy Ahrens, et autres
Publié: (2024)

Minimum Stable Cut and Treewidth
par: Lampis, Michael
Publié: (2021)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
par: Lill, Jonas, et autres
Publié: (2024)

Pseudodeterministic Algorithms for Minimum Cut Problems
par: Agarwala, Aryan, et autres
Publié: (2025)

Parameterized Critical Node Cut Revisited
par: Knop, Dušan, et autres
Publié: (2025)

Parameterized Max Min Feedback Vertex Set
par: Lampis, Michael, et autres
Publié: (2023)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
par: Bhaskar, Umang, et autres
Publié: (2025)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
par: Kratochvíl, Jan, et autres
Publié: (2020)

A tight quasi-polynomial bound for Global Label Min-Cut
par: Jaffke, Lars, et autres
Publié: (2022)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
par: Kenig, Batya
Publié: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
par: Adriaens, Florian, et autres
Publié: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
par: S., Karthik C., et autres
Publié: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
par: Scheder, Dominik, et autres
Publié: (2025)

The communication complexity of distributed estimation
par: Gopalan, Parikshit, et autres
Publié: (2025)

Parameterized complexity of reconfiguration of atoms
par: Cooper, Alexandre, et autres
Publié: (2021)

On the complexity and approximability of Bounded access Lempel Ziv coding
par: Cicalese, Ferdinando, et autres
Publié: (2024)

On girth and the parameterized complexity of token sliding and token jumping
par: Bartier, Valentin, et autres
Publié: (2020)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
par: Enright, Jessica, et autres
Publié: (2020)

The complexity of testing all properties of planar graphs, and the role of isomorphism
par: Basu, Sabyasachi, et autres
Publié: (2021)

Clustering with Locally Bounded Ignorance
par: Garvardt, Jaroslav, et autres
Publié: (2026)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
par: Yang, Yang
Publié: (2024)

Local Enumeration: The Not-All-Equal Case
par: Gurumukhani, Mohit, et autres
Publié: (2025)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
par: Johnson, Matthew, et autres
Publié: (2022)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
par: Esmer, Barış Can, et autres
Publié: (2022)

Complexity of Local Search for Euclidean Clustering Problems
par: Manthey, Bodo, et autres
Publié: (2023)

The Query Complexity of Local Search and Brouwer in Rounds
par: Brânzei, Simina, et autres
Publié: (2020)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
par: Dvořák, Pavel, et autres
Publié: (2022)

The Query Complexity of Local Search in Rounds on General Graphs
par: Brânzei, Simina, et autres
Publié: (2026)

Finding One Local Optimum Is Easy -- but What About Two?
par: Kobayashi, Yasuaki, et autres
Publié: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
par: Balzereit, Kaja, et autres
Publié: (2024)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
par: Grüttemeier, Niels, et autres
Publié: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2024)

On the complexity of global Roman domination problem in graphs
par: Reddy, Sangam Balchandar, et autres
Publié: (2026)

An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication
par: Sun, Yinqi
Publié: (2026)

Geometric Interpretation of 3-SAT and Phase Transition
par: Gillet, Frederic
Publié: (2025)

Hardness and Algorithmic Results for Roman \{3\}-Domination
par: Reddy, Sangam Balchandar
Publié: (2025)