AI Paper Atlas

Research map / Learning theory and algorithms / Combinatorial and search optimization

Equitable Stable Matchings in Quadratic Time

Nikolaos Tziavelis, Ioannis Giannakopoulos, Katerina Doka, Nectarios Koziris, Panagiotis Karras

NeurIPS 2019 · Learning theory and algorithms › Combinatorial and search optimization · approach: Heuristic and local search algorithms · 4 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Add random moves with probability p about 0.125 to rotation-based local search (ablation)iBILS · Discrete data (3 sizes, 2000 instances per size)sex-equality costImproved
Add random moves (p > 0) to breakmarriage-based local search (ablation)BILS · Uniform, Discrete, Gaussian datasex-equality costHurt
Replace breakmarriage operations with fine-grained rotations in lattice local search (iBILS vs BILS)BILS · Synthetic U, D, G (Figures 1, 2)runtime and costImproved
Start local search from the PowerBalance output instead of an extreme lattice position (Hybrid vs BILS)local search · Synthetic data up to n=4000runtime scalabilityImproved
Add local search after PowerBalance (Hybrid, HMS vs PowerBalance alone)PowerBalance · Synthetic data up to n=4000balance and sex-equality costImproved
Use multiple evenly placed PowerBalance termination points as local search starts (HMS vs Hybrid)Hybrid · Discrete data (Figure 1f)sex-equality costImproved
Use SDA-based PowerBalance instead of DACC with the same proposal strategyproposal-based methods · Synthetic data, both cost metricsbalance and sex-equality costImproved
Use iBILS/HMS instead of APPROXAPPROX · Uniform and Gaussian, n=4000SEq ratio over DAImproved
Use APPROX instead of iBILS on Discrete dataiBILS · Discrete, n=4000SEq ratio over DAHurt
Use any heuristic versus the one-side-biased solution on UniformDiscrete dataall algorithms · UniformDiscrete (Figures 1d, 1h, 3d)balance and SEqNo clear effect
Set PowerBalance round limit to Theta(n log2 n) rounds (ablation)PowerBalance · 100 instances per sizesex-equality costImproved

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy