Magíster en Gestión de Operaciones / Dada una colección de ciudades y el costo de viajar entre cualquier par de ella, el problema del vendedor viajero, que denotaremos como TSP (traveling salesman problem en inglés), consiste en encontrar el tour menos costoso que visita todas las ciudades al menos una vez retornando al punto inicial. En su forma métrica este problema es NP-duro, y por lo tanto no existe un algoritmo en tiempo polinomial que lo resuelva, salvo que P=NP. Para el caso métrico, Christofides diseñó en el año 1976 un 3/2-algoritmo de aproximación, el cual despertó una gran curiosidad con respecto a la aproximabilidad del problema. Sin embargo, y pese a los grandes esfuerzos efectuados en investigación, el algoritmo de Christofides es el de mejor garantía hasta el día de hoy. Recientemente han habido varios mejoras importantes con respecto a la aproximabilidad en casos especiales de TSP métrico. En el año 2011 Oveis Gharan et al. diseñaron un (3/2-ε)-algoritmo de aproximación para el caso graph-TSP, donde la distancia métrica entre cada par de ciudades está dada por el menor número de arcos necesarios para conectarlas por un camino dentro de un grafo sin pesos. En el mismo año Mömke y Svensson mejoran el resultado a 1.461, mientras Mucha en el 2012 mejora la garantía del algoritmo a 13/9. En el caso de que el grafo es cúbico de n vértices y 2-conexo, el algoritmo de Mömke y Svensson entrega un tour de largo menor a (4/3)n, resultado obtenido también por Boyd et al. en el año 2011. En este trabajo estudiamos el problema graph-TSP en distintas variantes de grafos cúbicos. Primero estudiamos el caso en que el grafo es planar, cúbico, bipartito y 3-conexo, el cual es un caso interesante desde el punto de vista de teoría de grafos ya que, según la conjetura de Barnette de hace más de 40 años estos grafos serían Hamiltonianos. En esta clase de grafos, conocidos como grafos de Barnette, mostramos que en un grafo de n vértices existe un tour de largo a lo más (4/3-1/18)n. Luego relajamos las condiciones sobre el grafo, quitando la hipótesis de planaridad e imponiendo que sea cúbico, bipartito y 2-conexo, caso en el cual mostramos que existe un tour de largo a lo más (4/3-1/108)n. Finalmente, estudiamos el caso en que el grafo es solamente cúbico y 2-conexo. En este caso nos basamos en las técnicas de Boyd et al. para mostrar que existe un tour de largo a lo más (4/3-1/61236)n. En cada caso mostramos que el tour se puede encontrar en tiempo polinomial, y como n es naturalmente una cota inferior del valor de graph-TSP, cada uno de los resultados obtenidos se traduce en un algoritmo de aproximación. Además, como n es una cota inferior de la relajación de Held & Karp, que es una conocida formulación para TSP como programa lineal, obtenemos como consecuencia que el gap de integralidad de TSP con respecto a esta relajación es acotado superiormente por (4/3-1/18) para el caso de Barnette, (4/3-1/108) para el caso cúbico, bipartito y 2-conexo, y (4/3-1/61236) para el caso cúbico y 2-conexo.

Magíster en Ciencias de la Ingeniería, Mención Transporte / Ingeniero Civil / Este trabajo considera programas de viajero frecuente ofrecidos por una firma de carácter monopólico, la cual ofrece a sus consumidores una cantidad de millas y un precio. La firma se enfrenta a dos tipos de consumidores indistinguibles, un viajero de negocios, quien viaja por obligación y gran parte de la tarifa la cancela su empleador - tercer pagador - y un viajero de ocio, quien viaja por gusto y la decisión de viajar es endógena. Existen tres etapas de análisis: demanda inelástica para ambos tipos de viajeros, elasticidad especial para el viajero de ocio y elasticidad para ambos viajeros. Las dos primera etapas se separan en dos casos: cuando el empleador no posee un precio máximo que está dispuesto a pagar, precio de reserva y cuando si lo posee Se aprecia que el tercer pagador provoca una ineficiencia en términos económicos, ya que el viajero de negocios recibe más millas que las eficientes, en cambio el viajero de ocio recibe una cantidad menor. El precio de reserva genera que el viajero de negocios reciba menos millas y el viajero de ocio una mayor cantidad. Los precios cobrados a los viajeros de ocio aumentan entre el primer y el segundo caso ya que la firma debe recuperar el costo de las millas adicionales. La utilidad de los viajeros de negocio aumenta al existir precio de reserva y la de los viajeros de ocio se mantiene sin variación en cero, debido a la demanda inelástica. Incluir elasticidad espacial replica en términos de millas, lo analizado anteriormente. El precio de reserva provoca un aumento de la utilidad de ambos tipos de viajeros, con lo cual el análisis en precios varía drásticamente, pues una mayor cantidad de millas no necesariamente generan un alza de precio, ya que la elasticidad puede generar que un aumento de millas sea recibido como una disminución del precio. La elasticidad en el viajero de negocios se incluye a través de una distribución del precio de reserva, la cual se puede concluir fácilmente que es una extensión del modelo con elasticidad espacial para el viajero de ocio, esta forma de inclusión no replica otros casos de monopolios enfrentados a demandas doblemente elásticas. Finalmente los resultados indican que el tercer pagador provoca ineficiencias económicas, las cuales pueden ser contrarrestadas por la existencia del precio de reserva. Se debe considerar que al no poder analizar en forma generar el comportamiento del precio con la inclusión del precio de reserva, pueden existir casos, donde paradójicamente un mayor precio observado, este generando un mercado con mejor cobertura.

Magíster en Ciencias de la Ingeniería, Mención Transporte. Ingeniero Civil Matemático / En este trabajo se propone un modelo teórico que considera la existencia de dos tipos de viajeros, de negocio y de ocio, quienes no son distinguibles por la aerolínea monopólica ex-ante, lo que es la fuente de un problema de selección adversa. Consideramos también que los viajeros de negocio no pagan la totalidad de su ticket, el que es financiado total o parcialmente por su empleador, lo que genera un problema tipo principal-agente entre ellos. Se modela el problema de discriminación de precios de segundo grado de la aerolínea, la cual ofrece un programa de viajeros frecuentes y que intenta separar a las clases de viajeros ofreciendo diferentes combinaciones de precios y recompensas, enfocado en el caso donde las recompensas están ligadas a alguna variable del problema, a saber, distancia volada o tarifa pagada. Inicialmente se analiza el caso donde la aerolínea sirve a un único mercado, encontrando que en la fase de diseño del programa, cuando los parámetros de demanda son tomados como sus valores esperados (el escenario ex-ante), estos programas son equivalentes a aquel en donde las recompensas pueden ser movidas libremente. Sin embargo, mostramos que el programa basado en la tarifa pagada le permite a la aerolínea responder a cambios en la demanda de manera más cercana a la óptima que el programa por distancia volada, lo que implica que, bajo ciertas condiciones, alcance un profit estrictamente mayor en el escenario ex-post. Respecto de la asignación de recompensas, se observa que la existencia de un tercer pagador genera ineficiencias económicas, en tanto que a los viajeros de negocio se le asignan más recompensas que lo óptimo socialmente, como medio para cobrar tarifas mayores. Posteriormente, se estudia el comportamiento de la firma al servir a dos mercados, con la posibilidad de ajustar un único programa. Al estudiar el programa por distancia volada se aprecia que este asigna recompensas más altas que lo óptimo para ambas clases del mercado con la distancia más larga, y menores que lo óptimo para el mercado con la distancia más corta. Este hecho provoca que los precios sigan la misma tendencia, siendo subóptimamente altos en el mercado con la mayor distancia. Por otro lado, el programa por tarifa pagada termina considerando ambos mercados como uno único, realizando asignaciones intermedias de precios y recompensas para ambas clases respecto al comportamiento óptimo, no existiendo por tanto dispersión de precios versus distancias de los mercados. Mostramos que al introducir elasticidad, bajo ambos programas existe dispersión de precios versus distancia, siendo mayor bajo un programa por distancia volada, lo que es consistente con la data recolectada para Southwest Airlines. Finalmente, se prueba que si las distancias de los mercados son muy cercanas, puede ser conveniente utilizar un programa por distancia volada, pero para redes de destinos muy heterogéneas en distancia, el programa por tarifa pagada le permite a la firma alcanzar un mayor profit.

This dissertation examines how Philippine (or Filipino) authors emphasise the need for articulating or “re/membering” cultural identity. The researcher mainly draws from the theory of Caribbean critic, Stuart Hall, who views cultural identity as an articulation which allows “the fragmented, decentred human agent” to be considered as one who is both “subject-ed” by power but/and one who is capable of acting against those powers (Grossberg 1996 [1986]: 157, emphasis mine). Applied to the Philippine context, this writer argues that, instead of viewing an apparent fragmented Filipino identity as a hindrance to “defining” cultural identity, she views the “damaged” (Fallows 1987) Filipino history as a the material itself which allows articulation of identity. Instead of reducing the cultural identity of a people to what-they-could-have-been-had-history-not-intervened, she puts forward a vision of identity which attempts to transfigure these “damages” through the efforts of coming-to-terms with history. While this point of view has already been shared by other critics (such as Feria 1991 or Dalisay 1998:145), the author’s contribution lies in presenting re/membering to describe a specific type of articulation which neither permits one to deny wounds of the past nor stagnate in them. Moreover, re/membering allows one to understand continuous re-articulations of “new” identities (due to current migration), while putting an “arbitrary closure” (Hall) to simplistic re-articulations which may only further the “lines of tendential forces” (such as black or brown skin bias) or hegemonic practices. Written as such (with a slash),“re/membering” encapsulates the following three-fold meaning: (1) a “re-membering”, to indicate “a putting together of the dismembered past to make sense of the trauma of the present” (Bhabha 1994:63); as (2) a “re-membering” or a re-integration into a group and; as (3) “remembering” which implies possessing “memory or … set [ting] off in search of a memory” (Ricoeur 2004:4). As a morphological unit, “re/membering” designates, the ways in which Filipino authors try to articulate cultural identity through the routes of colonisation, migration and dictatorship. The authors studied in this thesis include: Carlos Bulosan, Bienvenido Santos, N.V.M. Gonzalez, Nick Joaquin, Frank Sionil José, Ninotchka Rosca, Jessica Hagedorn, and Merlinda Bobis. Sixty-years separate Bulosan’s America is in the Heart (1943) from Hagedorn’s Dream Jungle (2003). Analysis of these works reveals how articulation is both difficult and hopeful. On the one hand, authors criticize the lack of efforts and seriousness towards articulation of cultural identity as re/membering (coming to terms with the past, fostering belonging and cultivating memory). Not only is re/membering challenged by double-consciousness (Du Bois 1994), dismemberment and forgetting, moreover, its necessity is likewise hard to recognize because of pain, trauma, phenomena of splitting, escapist attitudes and preferences for a “comfortable captivity”. On the other hand, re/membering can also be described as hopeful by the way authors themselves make use of literature to articulate identity through research, dialogue, time, reconciliation and re-creation. Although painstaking and difficult, re/membering is important and necessary because what is at stake is an articulated Philippine cultural identity. However, who would be prepared to make the effort? ------ Cette thèse démontre que, pour les auteurs philippins, l’articulation ou « re/membering » l'identité culturelle, est nécessaire. Le chercheur s'appuie principalement sur la théorie de Stuart Hall, qui perçoit l'identité culturelle comme une articulation qui permet de considérer l’homme assujetti capable aussi d'agir contre des pouvoirs (cf. Grossberg 1996 [1986]: 157). Appliquée au contexte philippin, cet auteur soutient que, au lieu de la visualisation d'une identité fragmentée apparente comme un obstacle à une « définition » de l'identité culturelle, elle regarde l’histoire philippine «abîmée» (Fallows 1987) comme le matériel même qui permet l'articulation d’identité. Au lieu de réduire l'identité culturelle d'un peuple à ce qu’ ils auraint pû être avant les interventions de l’histoire, elle met en avant une vision de l'identité qui cherche à transfigurer ces "dommages" par un travail d’acceptation avec l'histoire. Bien que ce point de vue a déjà été partagé par d'autres critiques (tels que Feria 1991 ou Dalisay 1998:145), la contribution de l'auteur réside dans la présentation de « re/membering » pour décrire un type d'articulation sans refouler les plaies du passé, mais sans stagner en elles non plus. De plus, « re/membering » permet de comprendre de futures articulations de « nouvelles » identités culturelles (en raison de la migration en cours), tout en mettant une «fermeture arbitraire» (Hall) aux ré-articulations simplistes qui ne font que promouvoir des “lines of tendential forces” (Hall) (tels que des préjugés sur la couleur brune ou noire de peau) ou des pratiques hégémoniques. Rédigé en tant que telle (avec /), « re/membering » comporte une triple signification: (1) une «re-membering », pour indiquer une mise ensemble d’un passé fragmenté pour donner un sens au traumatisme du présent (cf. Bhabha, 1994:63); (2) une «re-membering» ou une ré-intégration dans un groupe et finalement, comme (3)"remembering", qui suppose la possession de mémoire ou une recherche d'une mémoire »(Ricoeur 2004:4). Comme unité morphologique, « re/membering » désigne la manière dont les auteurs philippins tentent d'articuler l'identité culturelle à travers les routes de la colonisation, les migrations et la dictature. Les auteurs inclus dans cette thèse sont: Carlos Bulosan, Bienvenido Santos, NVM Gonzalez, Nick Joaquin, Frank Sionil José, Ninotchka Rosca, Jessica Hagedorn, et Merlinda Bobis. Soixante ans séparent America is in the Heart (1943) du Bulosan et le Dream Jungle (2003) du Hagedorn. L'analyse de ces œuvres révèle la façon dont l'articulation est à la fois difficile et pleine d'espoir. D'une part, les auteurs critiquent le manque d'efforts envers l'articulation en tant que « re/membering » (confrontation avec le passé, reconnaissance de l'appartenance et cultivation de la mémoire). Non seulement est « re/membering » heurté par le double conscience (Du Bois 1994), le démembrement et l'oubli, en outre, sa nécessité est également difficile à reconnaître en raison de la douleur, les traumatismes, les phénomènes de scission, les attitudes et les préférences d'évasion pour une captivité "confortable" . En même temps, « re/membering » peut également être décrit comme plein d'espoir par la façon dont les auteurs eux-mêmes utilisent la littérature pour articuler l'identité à travers la recherche, le dialogue, la durée, la réconciliation et la re-création. Bien que laborieux et difficile, « re/membering » est important et nécessaire car ce qui est en jeu, c'est une identité culturelle articulée des Philippines. Mais qui serait prêt à l'effort?

This dissertation examines how Philippine (or Filipino) authors emphasise the need for articulating or “re/membering” cultural identity. The researcher mainly draws from the theory of Caribbean critic, Stuart Hall, who views cultural identity as an articulation which allows “the fragmented, decentred human agent” to be considered as one who is both “subject-ed” by power but/and one who is capable of acting against those powers (Grossberg 1996 [1986]: 157, emphasis mine). Applied to the Philippine context, this writer argues that, instead of viewing an apparent fragmented Filipino identity as a hindrance to “defining” cultural identity, she views the “damaged” (Fallows 1987) Filipino history as a the material itself which allows articulation of identity. Instead of reducing the cultural identity of a people to what-they-could-have-been-had-history-not-intervened, she puts forward a vision of identity which attempts to transfigure these “damages” through the efforts of coming-to-terms with history. While this point of view has already been shared by other critics (such as Feria 1991 or Dalisay 1998:145), the author’s contribution lies in presenting re/membering to describe a specific type of articulation which neither permits one to deny wounds of the past nor stagnate in them. Moreover, re/membering allows one to understand continuous re-articulations of “new” identities (due to current migration), while putting an “arbitrary closure” (Hall) to simplistic re-articulations which may only further the “lines of tendential forces” (such as black or brown skin bias) or hegemonic practices.<p><p>Written as such (with a slash),“re/membering” encapsulates the following three-fold meaning: (1) a “re-membering”, to indicate “a putting together of the dismembered past to make sense of the trauma of the present” (Bhabha 1994:63); as (2) a “re-membering” or a re-integration into a group and; as (3) “remembering” which implies possessing “memory or … set [ting] off in search of a memory” (Ricoeur 2004:4). As a morphological unit, “re/membering” designates, the ways in which Filipino authors try to articulate cultural identity through the routes of colonisation, migration and dictatorship. <p><p>The authors studied in this thesis include: Carlos Bulosan, Bienvenido Santos, N.V.M. Gonzalez, Nick Joaquin, Frank Sionil José, Ninotchka Rosca, Jessica Hagedorn, and Merlinda Bobis. Sixty-years separate Bulosan’s America is in the Heart (1943) from Hagedorn’s Dream Jungle (2003). Analysis of these works reveals how articulation is both difficult and hopeful. On the one hand, authors criticize the lack of efforts and seriousness towards articulation of cultural identity as re/membering (coming to terms with the past, fostering belonging and cultivating memory). Not only is re/membering challenged by double-consciousness (Du Bois 1994), dismemberment and forgetting, moreover, its necessity is likewise hard to recognize because of pain, trauma, phenomena of splitting, escapist attitudes and preferences for a “comfortable captivity”. <p><p>On the other hand, re/membering can also be described as hopeful by the way authors themselves make use of literature to articulate identity through research, dialogue, time, reconciliation and re-creation. Although painstaking and difficult, re/membering is important and necessary because what is at stake is an articulated Philippine cultural identity. However, who would be prepared to make the effort?<p>------<p><p>Cette thèse démontre que, pour les auteurs philippins, l’articulation ou « re/membering » l'identité culturelle, est nécessaire. Le chercheur s'appuie principalement sur la théorie de Stuart Hall, qui perçoit l'identité culturelle comme une articulation qui permet de considérer l’homme assujetti capable aussi d'agir contre des pouvoirs (cf. Grossberg 1996 [1986]: 157). Appliquée au contexte philippin, cet auteur soutient que, au lieu de la visualisation d'une identité fragmentée apparente comme un obstacle à une « définition » de l'identité culturelle, elle regarde l’histoire philippine «abîmée» (Fallows 1987) comme le matériel même qui permet l'articulation d’identité. Au lieu de réduire l'identité culturelle d'un peuple à ce qu’ ils auraint pû être avant les interventions de l’histoire, elle met en avant une vision de l'identité qui cherche à transfigurer ces "dommages" par un travail d’acceptation avec l'histoire. <p><p>Bien que ce point de vue a déjà été partagé par d'autres critiques (tels que Feria 1991 ou Dalisay 1998:145), la contribution de l'auteur réside dans la présentation de « re/membering » pour décrire un type d'articulation sans refouler les plaies du passé, mais sans stagner en elles non plus. De plus, « re/membering » permet de comprendre de futures articulations de « nouvelles » identités culturelles (en raison de la migration en cours), tout en mettant une «fermeture arbitraire» (Hall) aux ré-articulations simplistes qui ne font que promouvoir des “lines of tendential forces” (Hall) (tels que des préjugés sur la couleur brune ou noire de peau) ou des pratiques hégémoniques.<p><p>Rédigé en tant que telle (avec /), « re/membering » comporte une triple signification: (1) une «re-membering », pour indiquer une mise ensemble d’un passé fragmenté pour donner un sens au traumatisme du présent (cf. Bhabha, 1994:63); (2) une «re-membering» ou une ré-intégration dans un groupe et finalement, comme (3)"remembering", qui suppose la possession de mémoire ou une recherche d'une mémoire »(Ricoeur 2004:4). Comme unité morphologique, « re/membering » désigne la manière dont les auteurs philippins tentent d'articuler l'identité culturelle à travers les routes de la colonisation, les migrations et la dictature. <p><p>Les auteurs inclus dans cette thèse sont: Carlos Bulosan, Bienvenido Santos, NVM Gonzalez, Nick Joaquin, Frank Sionil José, Ninotchka Rosca, Jessica Hagedorn, et Merlinda Bobis. Soixante ans séparent America is in the Heart (1943) du Bulosan et le Dream Jungle (2003) du Hagedorn. L'analyse de ces œuvres révèle la façon dont l'articulation est à la fois difficile et pleine d'espoir. D'une part, les auteurs critiquent le manque d'efforts envers l'articulation en tant que « re/membering » (confrontation avec le passé, reconnaissance de l'appartenance et cultivation de la mémoire). Non seulement est « re/membering » heurté par le double conscience (Du Bois 1994), le démembrement et l'oubli, en outre, sa nécessité est également difficile à reconnaître en raison de la douleur, les traumatismes, les phénomènes de scission, les attitudes et les préférences d'évasion pour une captivité "confortable" .<p><p>En même temps, « re/membering » peut également être décrit comme plein d'espoir par la façon dont les auteurs eux-mêmes utilisent la littérature pour articuler l'identité à travers la recherche, le dialogue, la durée, la réconciliation et la re-création. Bien que laborieux et difficile, « re/membering » est important et nécessaire car ce qui est en jeu, c'est une identité culturelle articulée des Philippines. Mais qui serait prêt à l'effort? <p> / Doctorat en Langues et lettres / info:eu-repo/semantics/nonPublished