Copertina

On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Shi, Haoyan, Mehrotra, Sanjay
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Optimization and Control
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Min-Max Connected Multiway Cut
di: Tiwary, Hans Raj, et al.
Pubblicazione: (2026)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
di: Rohwedder, Lars, et al.
Pubblicazione: (2025)

Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems
di: Salem, Jad, et al.
Pubblicazione: (2024)

An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies
di: Chen, Yike, et al.
Pubblicazione: (2024)

Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs
di: Li, Tongyang, et al.
Pubblicazione: (2024)

Approximation Schemes for Sequential Hiring Problems
di: Segev, Danny, et al.
Pubblicazione: (2026)

Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
di: Encz, Koppány István, et al.
Pubblicazione: (2025)

Exploiting Low-Rank Structure in Max-K-Cut Problems
di: Stevens, Ria, et al.
Pubblicazione: (2026)

The Robust Bilevel Selection Problem
di: Henke, Dorothee
Pubblicazione: (2024)

New Approximation Guarantees for The Economic Warehouse Lot Scheduling Problem
di: Segev, Danny
Pubblicazione: (2024)

Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms
di: Housni, Omar El, et al.
Pubblicazione: (2024)

Generalized Assignment and Knapsack Problems in the Random-Order Model
di: Klimm, Max, et al.
Pubblicazione: (2025)

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

Differentiable Extensions with Rounding Guarantees for Combinatorial Optimization over Permutations
di: Nerem, Robert R., et al.
Pubblicazione: (2024)

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

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

Optimization of Next-Day Delivery Coverage using Constraint Programming and Random Key Optimizers
di: Brubaker, Kyle, et al.
Pubblicazione: (2025)

Sum-Of-Squares To Approximate Knapsack
di: Kothari, Pravesh K., et al.
Pubblicazione: (2025)

Cascading-Tree Algorithm for the 0-1 Knapsack Problem (In Memory of Heiner M{ü}ller-Merbach, a Former President of IFORS)
di: Moeini, Mahdi, et al.
Pubblicazione: (2024)

Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion
di: Cai, Yang, et al.
Pubblicazione: (2022)

Fully Subexponential Time Approximation Scheme for Product Partition
di: Costandin, Marius
Pubblicazione: (2024)

Improved Approximation Guarantees for Joint Replenishment in Continuous Time
di: Segev, Danny
Pubblicazione: (2024)

Economic Warehouse Lot Scheduling: Breaking the 2-Approximation Barrier
di: Segev, Danny
Pubblicazione: (2026)

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
di: Chen, Li, et al.
Pubblicazione: (2025)

The Fair Periodic Assignment Problem
di: van Lieshout, Rolf, et al.
Pubblicazione: (2025)

Improved Approximation Guarantees and Hardness Results for MNL-Driven Product Ranking
di: Segev, Danny, et al.
Pubblicazione: (2025)

On the Complexity of Bilevel Independent Set Problem
di: Muluk, Komal
Pubblicazione: (2026)

Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
di: Chandrasekaran, Karthekeyan, et al.
Pubblicazione: (2025)

Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
di: Tate, Reuben, et al.
Pubblicazione: (2024)

Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time
di: Objois, Étienne, et al.
Pubblicazione: (2025)

Learning-Augmented Algorithms for the Bahncard Problem
di: Zhao, Hailiang, et al.
Pubblicazione: (2024)

Robust Gittins for Stochastic Scheduling
di: Moseley, Benjamin, et al.
Pubblicazione: (2025)

Acceleration by Random Stepsizes: Hedging, Equalization, and the Arcsine Stepsize Schedule
di: Altschuler, Jason M., et al.
Pubblicazione: (2024)

Economic Warehouse Lot Scheduling: Approximation Schemes via Efficiently-Representable DP-Encoded Policies
di: Segev, Danny
Pubblicazione: (2026)

Parameterized Complexity of Scheduling Problems in Robotic Process Automation
di: Dvořák, Michal, et al.
Pubblicazione: (2026)

Solving the Probabilistic Profitable Tour Problem on a Tree
di: Angelelli, Enrico, et al.
Pubblicazione: (2022)

Distributionally Robust Newsvendor on a Metric
di: Foussoul, Ayoub, et al.
Pubblicazione: (2024)

Deriving the Gradients of Some Popular Optimal Transport Algorithms
di: Xie, Fangzhou
Pubblicazione: (2025)

Solving Linear Programs with Fast Online Learning Algorithms
di: Gao, Wenzhi, et al.
Pubblicazione: (2021)

A Faster Parametric Search for the Integral Quickest Transshipment Problem
di: Anapolska, Mariia, et al.
Pubblicazione: (2025)