The unsplittable stable marriage problem

The Gale-Shapley "propose/reject" algorithm is a wellknown procedure for solving the classical stable marriage problem. In this paper we study this algorithm in the context of the many-to-many stable marriage problem, also known as the stable allocation or ordinal transportation problem. W...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Dean, Brian C., Goemans, Michel X., Immorlica, Nicole
Formato:	Objeto de conferencia
Lenguaje:	Inglés
Publicado:	2006
Materias:	Ciencias Informáticas Gale- Shapley algorithm stable marriage problem Algorithms
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/24374
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-24374
record_format	dspace
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Inglés
topic	Ciencias Informáticas Gale- Shapley algorithm stable marriage problem Algorithms
spellingShingle	Ciencias Informáticas Gale- Shapley algorithm stable marriage problem Algorithms Dean, Brian C. Goemans, Michel X. Immorlica, Nicole The unsplittable stable marriage problem
topic_facet	Ciencias Informáticas Gale- Shapley algorithm stable marriage problem Algorithms
description	The Gale-Shapley "propose/reject" algorithm is a wellknown procedure for solving the classical stable marriage problem. In this paper we study this algorithm in the context of the many-to-many stable marriage problem, also known as the stable allocation or ordinal transportation problem. We present an integral variant of the Gale- Shapley algorithm that provides a direct analog, in the context of "ordinal" assignment problems, of a well-known bicriteria approximation algorithm of Shmoys and Tardos for scheduling on unrelated parallel machines with costs. If we are assigning, say, jobs to machines, our algorithm nds an unsplit (non-preemptive) stable assignment where every job is assigned at least as well as it could be in any fractional stable assignment, and where each machine is congested by at most the processing time of the largest job.
format	Objeto de conferencia Objeto de conferencia
author	Dean, Brian C. Goemans, Michel X. Immorlica, Nicole
author_facet	Dean, Brian C. Goemans, Michel X. Immorlica, Nicole
author_sort	Dean, Brian C.
title	The unsplittable stable marriage problem
title_short	The unsplittable stable marriage problem
title_full	The unsplittable stable marriage problem
title_fullStr	The unsplittable stable marriage problem
title_full_unstemmed	The unsplittable stable marriage problem
title_sort	unsplittable stable marriage problem
publishDate	2006
url	http://sedici.unlp.edu.ar/handle/10915/24374
work_keys_str_mv	AT deanbrianc theunsplittablestablemarriageproblem AT goemansmichelx theunsplittablestablemarriageproblem AT immorlicanicole theunsplittablestablemarriageproblem AT deanbrianc unsplittablestablemarriageproblem AT goemansmichelx unsplittablestablemarriageproblem AT immorlicanicole unsplittablestablemarriageproblem
bdutipo_str	Repositorios
_version_	1764820467044057088

The unsplittable stable marriage problem

Ejemplares similares