Cover Image

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nasre, Meghana, Nimbhorkar, Prajakta, Ranjan, Keshav
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms 05C85, 68W25
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Capacity Modification for Stable Matchings with Ties
by: Ranjan, Keshav, et al.
Published: (2024)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

Zero-free regions of partition functions with applications to algorithms and graph limits
by: Regts, Guus
Published: (2015)

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
by: Galby, Esther, et al.
Published: (2024)

A $4/3$ Approximation for $2$-Vertex-Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2023)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
by: Krishnaswamy, Ravishankar, et al.
Published: (2014)

Supermodular Maximization with Cardinality Constraints
by: Chen, Xujin, et al.
Published: (2025)

Young domination on Hamming rectangles
by: Gravner, Janko, et al.
Published: (2025)

Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
by: Friggstad, Zachary, et al.
Published: (2018)

Traffic-Oblivious Multi-Commodity Flow Network Design
by: Chimani, Markus, et al.
Published: (2025)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
by: Agrawal, Akanksha, et al.
Published: (2024)

A simple Path-based LP Relaxation for Directed Steiner Tree
by: Pashkovich, Kanstantsin, et al.
Published: (2026)

A Constant-factor Approximation for Weighted Bond Cover
by: Kim, Eun Jung, et al.
Published: (2021)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
by: Haslebacher, Sebastian
Published: (2025)

Almost and Approximate EFX for Few Types of Agents
by: HV, Vishwa Prakash, et al.
Published: (2025)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

Random-Order Online Independent Set of Intervals and Hyperrectangles
by: Garg, Mohit, et al.
Published: (2024)

Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities
by: Bai, Miao, et al.
Published: (2023)

The Telephone $k$-Multicast Problem
by: Hathcock, Daniel, et al.
Published: (2024)

A Bad Example for Jain's Iterative Rounding Theorem for the Cover Small Cuts Problem
by: Simmons, Miles, et al.
Published: (2025)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
by: Patzner, Julian, et al.
Published: (2024)

A $5$-Approximation Analysis for the Cover Small Cuts Problem
by: Simmons, Miles, et al.
Published: (2026)

Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity
by: Bansal, Ishan, et al.
Published: (2024)

Exact Set Packing in Multimodal Transportation with Ridesharing System for First/Last Mile
by: Gu, Qian-Ping, et al.
Published: (2025)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
by: Oum, Sang-il, et al.
Published: (2026)

Reconfiguring homomorphisms to reflexive graphs via a simple reduction
by: Mühlenthaler, Moritz, et al.
Published: (2024)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

Shortest two disjoint paths in conservative graphs
by: Schlotter, Ildikó
Published: (2023)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
by: Liu, Bowen
Published: (2025)

Strongly Sublinear Algorithms for Testing Pattern Freeness
by: Newman, Ilan, et al.
Published: (2021)

Covering and packing mixed-integer linear programs with a fixed number of constraints: Approximation and convex hull
by: Grobben, Kobe, et al.
Published: (2025)

A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
by: Ammann, Sabrina C. L., et al.
Published: (2024)

Optimal non-adaptive algorithm for edge estimation
by: Bishnu, Arijit, et al.
Published: (2025)

Improved Approximation Algorithms for the Expanding Search Problem
by: Griesbach, Svenja M., et al.
Published: (2023)

Shortest Paths without a Map, but with an Entropic Regularizer
by: Bubeck, Sébastien, et al.
Published: (2022)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

On the Average-Case Performance of Greedy for Maximum Coverage
by: Balkanski, Eric, et al.
Published: (2026)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
by: Huber, Michael Kiran
Published: (2024)

Amnesiac Flooding: Easy to break, hard to escape
by: Austin, Henry, et al.
Published: (2025)