On multi-source minimum cost spanning tree problems and agglomeration problems

Abstract

The problems involving network formation have been extensively studied in operations research and economics literature because many real-life situations can be modeled through them. A prominent example would be the minimal cost spanning tree problem (mcstp) which considers a group of agents located at different geographical points that need to be connected to a source to access a certain service. The agents will be served through connections which entail some cost and they do not care if the connection to the source is direct or indirect. The first objective of the problem is to find the minimal tree (mt) that connects all the agents to the source; some examples of algorithms proposed to find this mt are Kruskal (1956) and Bird (1957). The second objective is of the problem is to allocate the cost associated with the mt among the agents. Bird (1976), Feltkamp et al. (1994), Kar (2002), Dutta and Kar (2004), Bergantiños and Vidal-Puga (2007) propose several allocation rules. A variant of this problem occurs when there is more than one source. These sorts of problems generalize the classic mcstp when there is a single source and they are very useful since they can model more complex situations. The connection problem to minimum cost when there are multiple sources has been studied in different scenarios by Granot and Granot (1992), Hu (1974), Ravi et al. (1996), and Wu et al. (2000), among others. However, the problem of cost allocation among agents has been less studied. Rosenthal (1987) considers the case where all sources offer the same service and agents must be connected to at least one of them, he associates a cooperative game to the problem and studies the circumstances under which there is a non-empty core. Kuipers (1997) considers the problem where each source offers a different service and each agent wants to be connected to some of the sources. Bergantiños et al. (2016) study a particular case of Kuipers (1997) where each agent wants to be connected to all sources and propose a rule by extending some of the different definitions of the Folk rule for the classical problem. Therefore, the general objective of this research is to conduct an in-depth study of minimum cost spanning tree problems with multiple sources and to propose more solutions that are applicable to different contexts, starting with the most particular case (Begantiños et al., 2016) ) and seeking to extend these results to the other two scenarios.

Los problemas que involucran la formación de una red han sido estudiados ampliamente en la literatura de investigación de operaciones y economía debido a que muchas situaciones de la vida real pueden ser modeladas mediante estos. Un ejemplo destacado sería el problema del árbol de expansión de coste mínimo (mcstp), el cual considera un grupo de agentes ubicados en puntos geográficos diferentes que necesitan conectarse a una fuente para poder acceder a determinado servicio. Los agentes serán servidos a través de conexiones que implican un costo y no les importa si la conexión a la fuente es directa o indirecta. El primer objetivo del problema es encontrar el árbol de coste mínimo (mt) que conecte a todos los agentes con la fuente; algunos ejemplo de algoritmos propuestos para encontrar este mt son Kruskal (1956) y Prim (1957. El segundo objetivo del problema es asignar el coste asociado al mt entre los agentes. Bird (1976), Feltkamp et al. (1994), Kar (2002), Dutta y Kar (2004), Bergantiños y Vidal-Puga (2007) proponen varias reglas de asignación. Una variante de este problema se presenta cuándo existe más de una fuente. Este tipo de problemas generalizan el problema clásico de árbol de expansión de coste mínimo cuando existe una fuente única y son de gran utilidad que ya pueden modelar situaciones más complejas. El problema de conexión a coste mínimo cuando hay múltiples fuentes se ha estudiado en distintos escenarios por Granot and Granot (1992), Hu (1974), Ravi et al. (1996), and Wu et al. (2000), entre otros. Sin embargo, el problema de asignación de costos entre los agentes ha sido menos estudiado. Rosenthal (1987) considera el caso en el que todas las fuentes ofrecen el mismo servicio y los agentes deben estar conectados a al menos una de ellas, asocia un juego cooperativo al problema y estudia las circunstancias bajo las cuales se tiene un núcleo no vacío. Kuipers (1997) considera el problema donde cada fuente ofrece un servicio diferente y cada agente quiere estar conectado a algunas de las fuentes. Bergantiños et al (2016) estudian un caso particular de Kuipers (1997) donde cada agente quiere estar conectado a todas las fuentes y proponen una regla basada en extensiones de algunas de las diferentes definiciones de la regla Folk en el problema clásico. Por lo tanto el objetivo general de este trabajo de investigación es realizar un estudio a profundidad de problemas de árboles de expansión de coste mínimo con múltiples fuentes y proponer más soluciones que sean aplicables a diferentes contextos, comenzando por el caso más particular (Begantiños et al (2016)) y buscando extender estos resultados a los otros dos escenarios.

Os problemas que implican a formación dunha rede foron extensivamente estudados na literatura de investigación de operacións e economía porque moitas situacións da vida real poden ser modeladas polos mesmos. Un exemplo destacado é o problema das árboles de expansión de custo mínimo (mcstp), que considera un grupo de axentes situados en diferentes localizacións xeográficas que precisan conectarse a unha fonte, a fin de acceder a determinados servizos. Os axentes serán servidos a través de conexións que implica un custo e non lles importa se a conexión coa fonte é directa ou indirecta. O primeiro obxectivo do problema é atopar a árbore de custo mínimo (mt) que conecta a todolos axentes coa fonte; algúns exemplos de algoritmos propostos para atopar este mt son Kruskal (1956) e Prim (1957). O segundo obxectivo do problema é asignar o custo asociado á mt entre os axentes. Bird (1976), Feltkamp et al. (1994), Kar ( 2002), Dutta e Kar (2004), Bergantiños e Vidal-Puga (2007) propoñen varias regras de distribución. Unha variante deste problema ocorre cando hai máis dunha fonte. Este tipo de problemas xeneralizan o problema clásico da árbore de custo mínimo cando hai unha única fonte e son de gran utilidade xa que poden modelar situacións máis complexas. O problema de conexión a custo mínimo cando hai varias fontes foi estudada en diversos escenarios por Granot e Granot (1992), Hu (1974), Ravi et al. (1996), e Wu et al. (2000), entre outros. Con todo, o problema de asignación de custos entre os axentes foi menos estudado. Rosenthal (1987) considera o caso na que todas as fontes ofrecen o mesmo servizo e os axentes deben estar conectados a polo menos una delas, asocia un xogo cooperativo para estudar o problema e as circunstancias en que ten un núcleo non baleiro. Kuipers (1997) considera o problema no que cada fonte ofrece un servizo diferente e cada axente quere estar conectado a algunhas das fontes. Bergantiños et al (2016) estudaron un caso particular de Kuipers (1997), onde cada axente quere estar conectado a todas as fontes e propuxeron unha regra baseada en extensións de algunhas das diferentes definicións da regra Folk no problema clásico. Polo tanto, o obxectivo xeral desta investigación é realizar un estudo en profundidade dos problemas das árbores de expansión de custo mínimo con múltiples fontes e propoñer máis solucións que sexan aplicables a diferentes contextos, comezando co caso particular (Begantiños et al (2016)), e buscando ampliar estes resultados a os outros dous escenarios.