A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

The Stable Roommates Problem with Unranked Entries O problema dos colegas de quarto estáveis ​​com entradas não classificadas

Hiroaki SUTO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

A família de problemas de correspondência estável tem sido bem estudada em um amplo campo de áreas de pesquisa, incluindo economia, matemática e ciência da computação. Em geral, um exemplo de um problema de correspondência estável é dado por um conjunto de participantes que expressaram as suas preferências uns dos outros, e pede para encontrar uma correspondência “estável”, isto é, um emparelhamento dos participantes tal que nenhum participante não emparelhado prefira entre si aos seus parceiros designados. No caso do Problema dos Companheiros de Quarto Estáveis ​​(SR), sabe-se que dado um número par n de participantes, pode não existir uma correspondência estável que emparelhe todos os participantes, mas existem algoritmos eficientes para determinar se isso é possível ou não e, se for possível, produzir tal correspondência. Extensões comuns de RS permitem que as listas de preferências dos participantes sejam incompletas ou incluam indiferença. Permitir a indiferença, por sua vez, dá origem a diferentes definições possíveis de estabilidade, estabilidade super, forte e fraca. Embora instâncias que solicitam correspondência super e fortemente estável possam ser resolvidas com eficiência mesmo se as listas de preferências estiverem incompletas, o caso de estabilidade fraca é NP-completo. Examinamos um caso restrito de indiferença, introduzindo o conceito de sem classificação entradas. Para este tipo de instâncias, mostramos que o problema de encontrar um emparelhamento fracamente estável permanece NP-completo mesmo que cada participante tenha uma lista de preferências completa com no máximo duas entradas não classificadas, ou seja ela própria não classificada para até três outros participantes. Por outro lado, para os casos em que existem m pares aceitáveis ​​e existem no total k entradas não classificadas em todas as listas de preferências dos participantes, propomos um O(2kn2)-algoritmo de tempo e espaço polinomial que encontra uma correspondência estável ou determina que nenhuma existe na instância fornecida.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1412-1419
Data de publicação
2018/09/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E101.A.1412
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria

autores

Hiroaki SUTO
  Kyoto University
Aleksandar SHURBEVSKI
  Kyoto University
Hiroshi NAGAMOCHI
  Kyoto University

Palavra-chave