Abstract

Selected papers from the seventh Latin American Theoretical INformatics conference (LATIN) held in Valdivia, Chile, on March 2004, 2006 are presented. The paper by Ilya Baran, Erik Demaine, and Dmitriy Katz introduces an adaptive analysis of numerical integration, where they consider the problem of integrating a Lipschitz function with a small additive error using as few samples of the function as possible. The paper by Nayantara Bhatnagar, Dana Randall, Vijay Vazirani, and Eric Vigoda studies sampling and approximately counting matchings of a given size in a bichromatic environment. The paper by Marek Chrobak, Claire Kenyon, John Noga, and Neal E. Young, considers a number of variations of the incremental medians problem originally proposed by Mettu and Plaxton. The paper by Mariko Sakashita considers a variety of source location problems, and shows that the source location problem with edge-connectivity requirements in undirected networks is strongly NPhard.