Cover Image

Max-Cut with Multiple Cardinality Constraints

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Makarychev, Yury, Pittu, Madhusudhan Reddy, Vakilian, Ali
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

Constraint Satisfaction Problems with Advice
by: Ghoshal, Suprovat, et al.
Published: (2024)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
by: Makarychev, Yury
Published: (2026)

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs
by: Brown, Adam, et al.
Published: (2024)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

New and Improved Bounds for Markov Paging
by: Pabbaraju, Chirag, et al.
Published: (2025)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
by: Dong, Yinhao, et al.
Published: (2024)

Combinatorial Optimization using Comparison Oracles
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Streaming Max-Cut in General Metrics
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Local Max-Cut on Sparse Graphs
by: Schwartzman, Gregory
Published: (2023)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Max Cut with Small-Dimensional SDP Solutions
by: Chang, Hsien-Chih, et al.
Published: (2026)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
by: Dalirrooyfard, Mina, et al.
Published: (2025)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
by: Dalirrooyfard, Mina, et al.
Published: (2026)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
by: Dalirrooyfard, Mina, et al.
Published: (2024)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
by: Menand, Nicolas, et al.
Published: (2025)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
by: Doron-Arad, Ilan, et al.
Published: (2023)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
by: Anand, Aditya, et al.
Published: (2024)

Optimal Phylogenetic Reconstruction from Sampled Quartets
by: Arvanitakis, Dionysis, et al.
Published: (2026)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
by: Kurita, Kazuhiro, et al.
Published: (2022)

Efficient Implementation of the Global Cardinality Constraint with Costs
by: Schmied, Margaux, et al.
Published: (2025)

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
by: Stoian, Mihail
Published: (2026)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
by: Im, Sungjin, et al.
Published: (2025)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
by: Makarychev, Konstantin, et al.
Published: (2025)

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
by: Parekh, Ojas
Published: (2025)

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

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

Scalable Algorithms for Individual Preference Stable Clustering
by: Mosenzon, Ron, et al.
Published: (2024)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
by: Michel, Lukas, et al.
Published: (2023)

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
by: Ahmadian, Sara, et al.
Published: (2024)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)