Cover Image

Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Salem, Jad, Tate, Reuben, Eidenbenz, Stephan
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computers and Society Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
by: Shi, Haoyan, et al.
Published: (2024)

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

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

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

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

Optimizing for Fairness in Generalized Kidney Exchange: Theory and Computations
by: Chang, Claire, et al.
Published: (2026)

Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families
by: Tate, Reuben, et al.
Published: (2025)

The Better Solution Probability Metric: Optimizing QAOA to Outperform its Warm-Start Solution
by: Feeney, Sean, et al.
Published: (2024)

Fair Assortment Planning
by: Chen, Qinyi, et al.
Published: (2022)

Online Decision Making with Fairness over Time
by: Chen, Rui, et al.
Published: (2022)

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
by: Yavlovich, Ilay, et al.
Published: (2026)

A greedy approach for increased vehicle utilization in ridesharing networks
by: Makhdomi, Aqsa Ashraf, et al.
Published: (2023)

Min-Max Optimization Is Strictly Easier Than Variational Inequalities
by: Shugart, Henry, et al.
Published: (2025)

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

The Robust Bilevel Selection Problem
by: Henke, Dorothee
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)

On the Fair Comparison of Optimization Algorithms in Different Machines
by: Arza, Etor, et al.
Published: (2023)

On the Complexity of Bilevel Independent Set Problem
by: Muluk, Komal
Published: (2026)

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

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

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

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

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

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

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

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

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

Bounds for the Permutation Flowshop Scheduling Problem: New Framework and Theoretical Insights
by: Alejandro-Soto, J. A., et al.
Published: (2025)

A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
by: Lin, Tianyi, et al.
Published: (2022)

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

Optimization in Sanger Sequencing
by: Carpente, Luisa, et al.
Published: (2024)

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

Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
by: Zhong, Dawei, et al.
Published: (2024)

Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization
by: Chakrabarti, Shouvanik, et al.
Published: (2024)

The Restricted Inverse Optimal Value Problem under Weighted Bottle-neck Hamming distance on trees
by: Zhang, Qiao, et al.
Published: (2024)

Submodular Order Functions and Assortment Optimization
by: Udwani, Rajan
Published: (2021)

Extracting Dual Solutions via Primal Optimizers
by: Carmon, Yair, et al.
Published: (2024)

Isotropic Noise in Stochastic and Quantum Convex Optimization
by: Marsden, Annie, et al.
Published: (2025)

Quasi-Self-Concordant Optimization with Lewis Weights
by: Ene, Alina, et al.
Published: (2025)