Sesión Matemática DiscretaEstudio de una nueva modelización para problemas de locación de servicios.
María Inés Lopez Pujato
Universidad Nacional de Rosario (FCEIA), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los empaquetamientos limitados en grafos fueron inicialmente introducidos en [3]. Algunas variantes de este concepto han sido definidas y estudiadas desde aquel trabajo de 2010 (algunos pueden verse en [1, 2, 4]). Todas ellas modelan diferentes problemas de locación de servicios (perjudiciales pero necesarios), en los cuales se requiere que en las cercanías de cada usuario se ubique un número acotado de éstos. El objetivo en estos problemas es maximizar el número de servicios a ubicar.
Con el propósito de abordar nuevas situaciones que requieren relajar condiciones sobre algunos usuarios del servicio a instalar, en este trabajo introducimos una nueva variante de este concepto. Dado un grafo $G$ con conjunto de vértices $V$, un vector $\mathbf{k}=(k_v)$ de capacidades enteras no negativas y vectores enteros $\mathbf{l}=(l_v)$ y $\mathbf{u}=(u_v)$, una función $f : V \rightarrow \mathbf{Z}^+$ es una función empaquetadora relajada en $G$ si $l_v\leq f(v)\leq u_v$ para cada $v\in V$ y tal que, para aquellos vértices $v$ para los cuales $f(v) > l_v$, $f$ satisface que la suma de sus valores sobre la vecindad cerrada de $v$ es a lo sumo $k_v$. El peso de una función empaquetadora relajada $f$ es $f(V) = \sum_{v\in V}f(v)$. Consideramos el problema de hallar una función empaquetadora relajada de máximo peso (número de empaquetamiento relajado) en un grafo dado. Pretendemos modelar, entre otras, situaciones que requieren que la acotación del número de servicios sea solo en las cercanías del usuario $v\in V$ en el que efectivamente se instaló al menos $l_v$ servicios.
Estudiamos diferentes instancias del problema general y para algunas de ellas, hallamos el valor exacto del número de empaquetamiento relajado.
Mostramos que es NP-completo decidir si un grafo dado tiene una función empaquetadora relajada de máximo peso, a través de una reducción al problema del máximo conjunto estable con pesos en un grafo.
Remarcamos que, mientras que todas las versiones de problemas de empaquetamientos estudiados en la literatura son NP-completos para grafos bipartitos, esta nueva variante se resuelve en tiempo polinomial para instancias dadas por grafos bipartitos.
Trabajo en conjunto con: M. P. Dobson (UNR), E. Hinrichsen (UNR) y V. Leoni (Conicet-UNR).
Referencias
[1] Bai X., H. Chang, X. Li, More on limited packings in graphs, Journal of Combinatorial Optimization 40, (2020), 412–430.
[2] Dobson M. P., E. Hinrichsen, V. Leoni, On the complexity of the {k}-packing functionproblem, International Transactions in Operational Research 24 (2017), 347-354.
[3] Gallant R., G. Gunther, B. Hartnell, D. Rall, Limited packing in graphs, Discrete Applied Mathematics 158 Issue 12 (2010), 1357–1364.
[4] Hinrichsen E., V. Leoni, M. Safe, Labelled packing functions in graphs, Inf. Processing Letters 154 (2020), doi.org/10.1016/j.ipl.2019.105863.