Parameterized algorithms for stable matching with ties and incomplete lists

DOI10.1016/J.TCS.2018.03.015MaRDI QIDQ1708024zbMATH OpenOpenAlexWikidataFDO

Authors Deeksha Adil, Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi

Publication date 4 April 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.03.015

zbMATH Keywords

parameterized complexitystable matchingpreference list

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matching models (91B68)

Recommendations

• A \((1 + 1/e)\)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists
• scientific article; zbMATH DE number 1003296
• A sublinear parallel algorithm for stable matching
• Approximating stable matchings with ties of bounded size
• Parameterized algorithms for inclusion of linear matchings
• Mathematical models for stable matching problems with ties and incomplete lists
• Faster and simpler approximation of stable matchings
• Faster and simpler approximation of stable matchings

Cites work

• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• A 3/2-Approximation Algorithm for General Stable Marriage
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Separator Theorem for Planar Graphs
• College Admissions and the Stability of Marriage
• Fundamentals of parameterized complexity
• Hard variants of stable marriage.
• Minimum Edge Dominating Sets
• NP-complete stable matching problems
• Parameterized algorithms
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Polynomial kernels for hard problems on disk graphs
• Quickly excluding a planar graph
• Stable marriage and indifference
• Stable marriage with ties and bounded length preference lists
• The structure of stable marriage with indifference

Cited in

(10)

• On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• Solving hard stable matching problems involving groups of similar agents
• Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective
• Algorithms and complexity of strongly stable non-crossing matchings
• Slim tree-cut width
• Balanced stable marriage: how close is close enough?
• Balanced stable marriage: how close is close enough?
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Effective data reduction for strongly stable matching in very sparse graphs

This page was built for publication: Parameterized algorithms for stable matching with ties and incomplete lists

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708024)