196,995 research outputs found
The postman [music] /
No full textFor voice with piano.; Cover title.; Cover features image of a postman walking by a letter box, carrying his whistle in one hand and a bundle of letters in the other. "PMG" can be seen on his hat and jacket.; Publication date approximated from the Sydney morning herald, 17 December, 1949, Column 8, p. 1 (http://nla.gov.au/nla.news-article18140283).; Also available online http://nla.gov.au/nla.mus-vn5978911
postman always rings twice
No full textNovel by James M. Cain on which the film 'The Postman Always Rings Twice' was based, starring Lana Turner and John Garfiel
Postman Problems on Mixed Graphs
No full textThe mixed postman problem consists of finding a minimum cost tour of a mixed graph M = (V, E, A) traversing all its edges and arcs at least once. We prove that two well-known linear programming relaxations of this problem are equivalent. The extra cost of a mixed postman tour T is the cost of T minus the cost of the edges and arcs of M . We prove that it is to approximate the minimum extra cost of a mixed postman tour. A relate
New results on the Windy Postman Problem
No full text[EN] In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd zigzag inequalities, are Chvátal-Gomory inequalities of rank at most 2. Moreover, a branch-and-cut algorithm that incorporates two new separation algorithms for all the previously mentioned inequalities and a new heuristic procedure to obtain upper bounds are presented. Finally, the performance of a branch-and-cut algorithm over several sets of large WPP and MCPP instances, with up to 3,000 nodes and 9,000 edges (and arcs in the MCPP case), shows that, to our knowledge, this is the best algorithm to date for the exact resolution of the WPP and the MCPP. © 2010 Springer and Mathematical Optimization Society.The authors want to thank the three referees for their careful reading of the manuscript and for their many comments and suggestions that have contributed to improve the paper content and readability. In particular, several remarks regarding the discussion of C-G and mod-k inequalities were pointed out by one of the referees. A. Corberan, I. Plana and J.M. Sanchis wish to thank the Ministerio de Educacion y Ciencia of Spain (projects MTM2006-14961-C05-02 and MTM2009-14039-C06-02) for its support.Corberán, A.; Oswald, M.; Plana, I.; Reinelt, G.; Sanchís Llopis, JM. (2012). New results on the Windy Postman Problem. Mathematical Programming. 132(1-2):309-332. https://doi.org/10.1007/s10107-010-0399-xS3093321321-2Benavent E., Carrotta A., Corberán A., Sanchis J.M., Vigo D.: Lower bounds and heuristics for the windy rural postman problem. Eur. J. Oper. Res. 176, 855–869 (2007)Brucker P. The Chinese postman problem for mixed graphs. In Proceedings of international workshop. Lecture Notes in Computer Science 100, 354–366 (1981)Caprara A., Fischetti M.: -Chvátal-Gomory cuts. Math. Program. 74, 221–235 (1996)Caprara A., Fischetti M., Letchford A.N.: On the separation of maximally violated mod-k cuts. Math. Program. 87, 37–56 (2000)Christof, T., Loebel, A.: PORTA—a polyhedron representation algorithm www.informatik.uni-heidelberg.de/groups/comopt/software/PORTA/ (1998)Christofides, N., Benavent, E., Campos, V., Corberán, A., Mota, E.: An optimal method for the mixed postman problem. In Thoft-Christensen, P. (ed.) System Modelling and Optimization. Lecture Notes in Control and Information Sciences 59, Springer (1984)Corberán A., Plana I., Sanchis J.M.: Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems. Math. Program. 108, 79–96 (2006)Corberán A., Plana I., Sanchis J.M.: A branch & cut algorithm for the windy general routing problem and special cases. Networks 49, 245–257 (2007)Corberán, A., Plana I., Sanchis, J.M.: Arc routing problems: data instances. www.uv.es/corberan/instancias.htm (2007)Corberán A., Plana I., Sanchis J.M.: The windy general routing polyhedron: a global view of many known arc routing polyhedra. SIAM J. Discrete Math. 22, 606–628 (2008)Grötschel, M., Win, Z.: On the windy postman polyhedron. Report No. 75, Schwerpunktprogram der Deutschen Forschungsgemeinschaft, Universität Augsburg, Germany (1988)Grötschel M., Win Z.: A cutting plane algorithm for the Windy Postman Problem. Math. Program. 55, 339–358 (1992)Guan M.: On the Windy Postman Problem. Discrete Appl. Math. 9, 41–46 (1984)Minieka E.: The Chinese postman problem for mixed networks. Manage. Sci. 25, 643–648 (1979)Naddef D., Rinaldi G.: The symmetric traveling salesman polytope and its graphical relaxation: composition of valid inequalities. Math. Program. 51, 359–400 (1991)Oswald M., Reinelt G., Seitz H.: Applying mod-k cuts for solving linear ordering problems. TOP 17, 158–170 (2009)Papadimitriou C.H.: On the complexity of edge traversing. J. Assoc. Comput. Mach. 23, 544–554 (1976)Ralphs T.K.: On the mixed Chinese postman problem. Oper. Res. Lett. 14, 123–127 (1993)Wenger, K.: Generic Cut Generation Methods for Routing Problems. PhD Dissertation, University of Heidelberg, Germany (2004)Win, Z.: Contributions to Routing Problems. PhD Dissertation, University of Augsburg, Germany (1987)Win Z.: On the Windy Postman Problem on eulerian graphs. Math. Program. 44, 97–112 (1989)Zaragoza Martínez F.J.: Series-parallel graphs are windy postman perfect. Discrete Math. 308, 1366–1374 (2008
Poetry's total scandal : Poets and postmen in Antonio Skármeta’s El cartero de Neruda
No full textThe argument put forward here takes Antonio Skármeta's short novel El cartero de Neruda (Con ardiente paciencia) as a theorization of the relationship between poetry and politics, by way of the concept-metaphors (Mieke Bal) that are deployed in the novel. Skármeta stages the public role of poetry through the telling of a story about the poet Pablo Neruda and his postman Mario Jiménez. The relationship between poetry and politics is analysed with reference to Hazard Adams' concept of «the offense of poetry» and Roland Barthes' reflections on the total scandal of language in his essay «Écrivains et écrivants» (1964), here adapted as «the total scandal of poetry». In contradistinction to Barthes, who argues that the total scandal of language is impossible because of the absorption of scandalous language by the literary institution, Skármeta's short novel suggests that the total scandal of poetry is indeed possible when, as in the case of Pablo Neruda, Mario Jiménez and Salvador Allende, poetry becomes a constitutive part of a political project, within which it functions as a reminder of dignity and as the touchstone for political integrity
Evidence for X-ray emission from a large-scale filament of galaxies?
No full textCosmological simulations predict that a large fraction of the baryonic mass of the universe exists as 10(5)-10(7) K diffuse, X-ray-emitting gas, tracing low-density filament and sheetlike structures exterior to massive clusters of galaxies. If present, this gas helps reconcile the current shortfall in observed baryon counts relative to the predictions of the standard big bang model. We present here the discovery and analysis of a 5 sigma significance half-degree filamentary structure, which is present in both the I-band salary surface density and the unresolved X-ray emission in a deep ROSAT PSPC field. The estimated diffuse X-ray emission component of this structure has a surface brightness of similar or equal to 1.6 x 10(-16) ergs s(-1) cm(-2) arcmin(-2) (0.5-2 keV), comparable to the predictions for intercluster gas, and may represent a direct detection of this currently unconfirmed baryonic component
Min-Max K-vehicles Windy Rural Postman Problem
No full text[EN] In this article the Min-Max version of the windy rural postman problem with several vehicles is introduced. For this problem, in which the objective is to minimize the length of the longest tour in order to find a set of balanced tours for the vehicles, we present here an ILP formulation and study its associated polyhedron. Based on its partial description, a branch-and-cut algorithm has been implemented and computational results on a large set of instances are finally presented. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 54(4),216-226 2009Contract grant sponsor: Ministerio de Education y Ciencia of Spain: Contract gram number: MTM2006-14961-C05-02Benavent López, E.; Corberan, A.; Plana, I.; Sanchís Llopis, JM. (2009). Min-Max K-vehicles Windy Rural Postman Problem. Networks. 54(4):216-226. https://doi.org/10.1002/net.20334S216226544D. Ahr Contributions to multiple postmen problems 2004D. Ahr G. Reinelt “New heuristics and lower bounds for the min-max k -Chinese postman problem” Algorithms-ESA 2002, 10th Annual European Symposium, Rome, Italy, 2002, Lecture Notes in Computer Science 2461 R. Möring R. Raman Springer Berlin 2002 64 74Ahr, D., & Reinelt, G. (2006). A tabu search algorithm for the min–max k-Chinese postman problem. Computers & Operations Research, 33(12), 3403-3422. doi:10.1016/j.cor.2005.02.011D. Applegate R.E. Bixby V. Chvátal W. Cook Finding cuts in the TSP 1995Barahona, F., & Grötschel, M. (1986). On the cycle polytope of a binary matroid. Journal of Combinatorial Theory, Series B, 40(1), 40-62. doi:10.1016/0095-8956(86)90063-8Belenguer, J. M., & Benavent, E. (1998). Computational Optimization and Applications, 10(2), 165-187. doi:10.1023/a:1018316919294Benavent, E., Carrotta, A., Corberán, A., Sanchis, J. M., & Vigo, D. (2007). Lower bounds and heuristics for the Windy Rural Postman Problem. European Journal of Operational Research, 176(2), 855-869. doi:10.1016/j.ejor.2005.09.021N. Christofides V. Campos A. Corberán E. Mota An algorithm for the rural postman problem 1981Christofides, N., Campos, V., Corberán, A., & Mota, E. (1986). An algorithm for the Rural Postman problem on a directed graph. Netflow at Pisa, 155-166. doi:10.1007/bfb0121091Corberán, A., Plana, I., & Sanchis, J. M. (2008). The Windy General Routing Polyhedron: A Global View of Many Known Arc Routing Polyhedra. SIAM Journal on Discrete Mathematics, 22(2), 606-628. doi:10.1137/050640886Corberán, A., Plana, I., & Sanchis, J. M. (2007). A branch & cut algorithm for the windy general routing problem and special cases. Networks, 49(4), 245-257. doi:10.1002/net.20176Eiselt, H. A., Gendreau, M., & Laporte, G. (1995). Arc Routing Problems, Part II: The Rural Postman Problem. Operations Research, 43(3), 399-414. doi:10.1287/opre.43.3.399Frederickson, G. N., Hecht, M. S., & Kim, C. E. (1978). Approximation Algorithms for Some Routing Problems. SIAM Journal on Computing, 7(2), 178-193. doi:10.1137/0207017G. Ghiani D. Laganá G. Laporte R. Musmanno A branch-and-cut algorithm for the undirected capacitated arc routing problem 2007Ghiani, G., & Laporte, G. (2000). A branch-and-cut algorithm for the Undirected Rural Postman Problem. Mathematical Programming, 87(3), 467-481. doi:10.1007/s101070050007Golden, B. L., & Wong, R. T. (1981). Capacitated arc routing problems. Networks, 11(3), 305-315. doi:10.1002/net.3230110308Padberg, M. W., & Rao, M. R. (1982). Odd Minimum Cut-Sets andb-Matchings. Mathematics of Operations Research, 7(1), 67-80. doi:10.1287/moor.7.1.67Pearn, W. L. (1994). Solvable cases of the k-person Chinese postman problem. Operations Research Letters, 16(4), 241-244. doi:10.1016/0167-6377(94)90073-
On the generalized directed rural postman problem
No full textS.1143-1154The generalized directed rural postman problem (GDRPP) is a generic type of arc routing problem. In the present paper, it is described how many types of practically relevant single-vehicle routing problems can be modelled as GDRPPs. This demonstrates the versatility of the GDRPP and its importance as a unified model for postman problems. In addition, an exact and a heuristic solution method are presented. Computational experiments using two large sets of benchmark instances are performed. The results show high solution quality and thus demonstrate the practical usefulness of the approach.65Nr.
Algoritmos heurísticos de cobertura de arcos
No full textTese (doutorado) - Universidade Federal de Santa Catarina. Centro Tecnológico. Programa de Pós-Graduação em Engenharia de ProduçãoNos problemas de roteamento o objetivo é determinar um circuito de custo mínimo que cobre um dado conjunto de arcos ou nós de um grafo, sujeito a algumas restrições. Existem duas classes bem conhecidas de tais problemas, denominadas como o Problema de Caixeiro Viajante (PCV), e o Problema do Carteiro Chinês (PCC). Com raras exceções, todos os problemas já formulados nessas duas classes são NP-completos. Portanto, para os problemas de maior porte existem apenas soluções aproximadas. Nessa Tese foi considerado o problema de determinar um circuito de custo mínimo que cobre um dado subconjunto de arcos, de arestas e de nós de um grafo misto, sujeito a algumas restrições nos vértices (restrições que proíbem conversões indesejáveis nos cruzamentos de malhas urbanas). Obviamente, o PCV, PCC e a maior parte de suas variações, como: o Problema do Carteiro Chinês Misto e o Problema do Carteiro Rural são casos particulares deste problema geral. A solução proposta é baseada numa transformação polinomial do grafo que possibilita a solução do problema resultante como um PCV padrão. Resultados computacionais confirmam a eficiência do método na obtenção de soluções próxima a ótimas para problemas razoavelmente grandes
A Note On k Best Solutions To The Chinese Postman Problem
No full text. The K-best problems on combinatorial optimization problems, in which K best solutions are considered instead of an optimal solution under the same conditions, have widely been studied. In this paper, we consider the K-best problem on the famous Chinese postman problem and develop an algorithm that finds K best solutions. The time complexity of our algorithm is O(S(n; m) + K(n + m + log K + nT (n + m;m))) where S(s; t) denotes the time complexity of an algorithm for ordinary Chinese postman problems and T (s; t) denotes the time complexity of a post optimal algorithm for non-bipartite matching problems defined on a graph with s vertices and t edges. Key words. Combinatorial Optimization, Chinese Postman Problem, K-best Problem, T-join Problem, Matching Theory, Graph Theory AMS(MOS) subject classifications. 05C38, 05C45 1. Introduction. The Chinese postman problem is proposed by Mei-ko Kwan in [8] for the first time. The problem is interpreted as follows [10]. The postman delivers..
- …
