Cover Image

A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Proença, Nathan Benedetto, Silva, Marcel K. de Carli, Sato, Cristiane M., Tunçel, Levent
Format:	Preprint
Published:	2023
Subjects:	Optimization and Control 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

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

Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach
by: Proença, Nathan Benedetto, et al.
Published: (2026)

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

Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
by: Fujiwara, Hiroshi, et al.
Published: (2025)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

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

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
by: Schade, Jamico, et al.
Published: (2023)

Flow Shop Scheduling with Stochastic Reentry
by: von Aspern, Maximilian, et al.
Published: (2026)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
by: Wang, Chenhao
Published: (2025)

ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
by: Gallart, Joan Vendrell, et al.
Published: (2025)

Efficient Local and Tabu Search Strategies for Large-Scale Quadratic Integer Programming
by: Wang, Haibo, et al.
Published: (2024)

Multiplicative assignment with upgrades
by: Armbruster, Alexander, et al.
Published: (2025)

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

EPTAS for Hard Graph Cut Problems for Dense Graphs
by: Deguchi, Kaisei, et al.
Published: (2026)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
by: Manna, Bubai, et al.
Published: (2024)

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

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)

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)

On the Bidirected Cut Relaxation for Steiner Forest
by: Byrka, Jarosław, et al.
Published: (2024)

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

Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems
by: Duvignau, Romaric, et al.
Published: (2024)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
by: Bentert, Matthias, et al.
Published: (2024)

Vertex-ordering and arc-partitioning problems
by: Borsik, Nóra A., et al.
Published: (2025)

Integer programs with bounded subdeterminants and two nonzeros per row
by: Fiorini, Samuel, et al.
Published: (2021)

Separable convex optimization over indegree polytopes
by: Borsik, Nóra A., et al.
Published: (2025)

Prefix-bounded matrices
by: Borsik, Nóra A., et al.
Published: (2025)

On the Congruency-Constrained Matroid Base
by: Liu, Siyue, et al.
Published: (2023)

Complexity of polytope diameters via perfect matchings
by: Nöbel, Christian, et al.
Published: (2024)

Integer programs with nearly totally unimodular matrices: the cographic case
by: Aprile, Manuel, et al.
Published: (2024)

Totally $Δ$-modular IPs with two non-zeros in most rows
by: Kober, Stefan
Published: (2024)

Total Matching and Subdeterminants
by: Ferrarini, Luca, et al.
Published: (2023)

Algorithmic aspects of semistability of quiver representations
by: Iwamasa, Yuni, et al.
Published: (2024)

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

H-Planarity and Parametric Extensions: when Modulators Act Globally
by: Fomin, Fedor V., et al.
Published: (2025)

On Connections Between Association Schemes and Analyses of Polyhedral and Positive Semidefinite Lift-and-Project Relaxations
by: Au, Yu Hin, et al.
Published: (2020)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)