Seminarios 2012

2012-12-19:

Author: Maya Stein, DIM-CMM, Universidad de Chile

Where: Sala 33, DII, 14:30-16:00

Title: The approximate Loebl-Komlos-Sos conjecture

Abstract: The talk is on the approximate solution of the Loebl-Komlos-Sos conjecture. This is a conjecture in extremal graph theory, it asks whether a median degree of at least k guarantees all trees of order k + 1 as subgraphs. Together with Hladky, Piguet, Komlos, Simonovits, Szemeredi we solved the approximate version, as a first step towards the exact solution. We employ a structural tool (which might be interesting on its own) that decomposes any given graph into several parts, one of these being ‘classical’ regular pairs, the others more adapted to our possibly sparse setting.

 

2012-12-12:

Author: Pablo Pérez Lantero, Universidad de Valparaíso

Where: Sala 33, DII, 14:30-16:00

Title: Maximum Weight Planar Boxes

Abstract: Given a finite set of n points in the plane, where each point is associated with a weight (positive or negative), the Maximum Weight Box problem consists in finding an axis-aligned rectangle maximizing the sum of the weights of the points that it contains. We propose algorithms solving this problem which run in the worst case in O(n2) time, and much less on other classes of instances. These algorithms improve upon previous results where the general Maximum Weight Box problem was solved in O(n2 log n) time [Cortés et al., J.Alg. 2009] and a particular case of it with weights in the set {-1,+1} was also solved in time within O(n2 log n) [Dobkin et al., J.Comput.Syst.Sci. 1996]. We also present some other known results in which the maximum weight shape to be found is a convex polygon, a half plane, and a stripe.

This is a joint work with Jeremy Barbay, Timothy Chan, and Gonzalo Navarro.

 

2012-12-5:

Author: Julián Mestre, University of Sydney

Where: Sala 33, DII, 14:30-16:00

Title: Another look at longest wait first for broadcast scheduling

Abstract: En el problema de broadcast scheduling un servidor recibe en forma on-line pedidos de transmisión de ciertos ítems y debe decidir cuál ítem transmitir en cada unidad de tiempo. El objetivo es minimizar el tiempo promedio de espera de los pedidos (average flow time). LWF es una heurística que transmite el ítem con el máximo tiempo de espera. En evaluaciones experimentales LWF exhibe la mejor performance entre un conjunto de heurísticas naturales. Desde un punto de vista teórico, Edmonds y Pruhs, y más tarde Chekuri y otros, demostraron que LWF es O(1)-competitivo en el modelo de aumentación de recursos donde el servidor puede transmitir a una velocidad mayor que la solución óptima.

En esta charla hablaremos de las técnicas usadas en el análisis de LWF y, si el tiempo lo permite, esbozaremos cómo mejorar el análisis.

 

2012-11-28:

Author: Jozef Skokan, London School of Economics

Where: Sala 33, DII, 14:30-16:00

Title: Matching and Tiling in Multipartite Graphs

Abstract:

Matching theory is a large field with many directions of research, both in practical algorithms and combinatorial theory. In this talk I will aim to show some of the breadth of the subject and some recent advances. In particular, theorems of Hajnal & Szemeredi and Alon & Yuster give sufficient minimum degree conditions for the existence of a perfect matching/tiling in a given graph G. We shall discuss how to improve these conditions in the case when G is a k-partite graph.

 

 

Note:

The seminar will not be held on Wed Nov 21st.

2012-11-14:

Author:

Christoph Dürr, Researcher at LIP6, Université Pierre et Marie Curie, Paris, France.

Where:

Sala 33, DII, 14:30-16:00.

Title:

The Interval ordering problem

Abstract:

We present an open problem. For a given set of intervals on the real line, we consider the problem of ordering the intervals with the goal of minimizing an objective function that depends on the exposed interval pieces (that is, the pieces that are not covered by earlier intervals in the ordering). For the constraint satisfaction problem motivation we have in mind, the objective function is 2x where x is the total exposed length. The complexity status of this problem is open.We present polynomial-time algorithms for several natural special cases of the problem that cover the situation where the interval boundaries are agreeably ordered and the situation where the interval set is laminar. Also the bottleneck variant of the problem is shown to be solvable in polynomial time. Finally we prove that the general problem is NP-hard, and that the existence of a constant-factor-approximation algorithm is unlikely.

Joint work with with Maurice Queyranne, Frits C.R. Spieksma, Fabrice Talla Nobibon and Gerhard J. Woeginger.

 

2012-11-07:

Author:

Qingxia Kong, UAI.

Where:

Sala 33, DII, 14:30-16:00.

Title:

Scheduling Arrivals to a Stochastic Service Delivery System using Copositive Cones.

Abstract:

In this talk, we investigate a stochastic appointment scheduling problem in an outpatient clinic with a single doctor. The number of patients is fixed, and the scheduling problem is to determine an arrival order and an appointment time for each patient. The service durations of the patients are stochastic, and only the mean and covariance estimates are known. We do not assume any exact distributional form of the service durations, and solve for distributionally robust schedules that minimize the expectation of the weighted sum of patients waiting time and doctors overtime. We formulate this scheduling problem as a convex conic optimization problem with a tractable semi-definite relaxation. Using the primal-dual optimality conditions, we prove several interesting structural properties of the optimal schedules. We develop an efficient semidefinite relaxation of the conic program, and show that we can still obtain near optimal solutions on benchmark instances in the existing literature. We apply our approach to develop a practical appointment schedule at an eye clinic that can significantly improve the efficiency of the appointment system in the clinic, compared to an existing schedule.

 

2012-10-31:

Author:

Oscar C. Vásquez, Université Pierre et Marie Curie(Paris VI)

Where:

Sala 33, DII. 14:30-16:00.

Title:

Energía en sistemas informáticos: optimización y mecanismos de incitación.

Abstract:

Nosotros discutimos sobre los mecanismos de incitación en sistemas informáticos con muchos usuarios. El objetivo es encontrar un medio de facturación de la energía consumida entre los usuarios, considerando que ellos adoptan un comportamiento en función de la calidad de servicio entregada y su consumo de energía. Concretamente, consideramos un sistema con un procesador que funciona con una velocidad variable. Una gran velocidad permite la rápida terminación de las tareas, dando una buena calidad de servicio, pero una velocidad menor permite un bajo consumo de energía. A partir de la situación descrita, estudiamos diferentes juegos, en función de la sensibilidad de los usuarios al tiempo de finalización de sus tareas. Nuestra discusión también aborda los problemas de optimización asociados, su complejidad y las técnicas de cálculo exacto y aproximaciones.

Este trabajo es realizado en conjunto con Christoph Dürr (LIP 6-Paris VI)

 

2012-10-24:

Author:

Mike Wagner, UW.

Where:

DII, Sala 22, 14:30-16:00

Title:

The Benefit/Detriment of Information in Coordinating Supply Chains

Abstract:

Our talk proves that information is a double-edged sword in supply chain coordination. We study a simple supply chain consisting of one supplier and one retailer, where one firm knows the probabilistic distribution of demand and the other only knows the mean and variance. We show that this informational asymmetry either reduces or exacerbates the double marginalization effect for a wholesale price contract. We study how the direction of asymmetry, level of uncertainty, economics and game theoretic considerations (e.g., does the firm with full information know that the other firm lacks information) affect double marginalization and the performance of the entire supply chain. Furthermore, we show how these factors affect the individual firms’ performance. In certain cases, we have a full theoretical characterization, though in others we’re limited to computational results; these latter cases are promising directions for future research.

 

2012-10-17:

Author:

Jorge Vera.

Where:

DII, Sala 33, 14:30-16:00.

Title:

Planificación de Producción Robusta: ideas y preguntas.

Abstract:

En esta presentación mostraré algunos resultados que hemos desarrollado, basados en una situación industrial real, y que se relacionan Con el problema de Planificación de Producción que enfrenta la división de aserraderos de una compañía forestal. Generalmente la Planificación de Producción se realiza en el mediano plazo y después se programa más en detalle en el corto plazo usando modelos “tradicionales” de Programación lineal. Sin embargo, existen diversas incertidumbres que son difíciles de abordar y que producen inconsistencias en esta planificación intertemporal. Hemos usado optimización robusta como método para la planificación táctica de modo que se puedan obtener planificaciones de corto plazo más eficientes y factibles. En este contexto, una de las preguntas que surge es cuál es el “nivel óptimo de robustez” que debe tener el plan y si acaso es posible calcular probabilidades de cumplimento en el corto plazo para distintos escenarios. Discutiré estas preguntas además de mostrar algunos de los resultados ya obtenidos.

 

2012-10-10:

Author:

Jouni Siren, University of Helsinki, Finland.

Where:

DII, sala 33, 14:30-16:00.

Title:

Distribution-aware compressed full-text indexes.

Abstract:

Compressed suffix arrays allow searching for arbitrary substrings of a text efficiently, while storing the text in a similar space as when compressed with common compressors such as gzip or bzip2. They are usually based on the Burrows-Wheeler transform (BWT), a permutation of the text closely related to the suffix array. The standard solution to locate the occurrences of a pattern is to sample a number of text positions explicitly, and to derive the rest of the positions by using the BWT. This takes time proportional to the distance between the located position and the nearest sampled position.

The sampled positions are usually selected at regular intervals, optimizing the worst-case performance. Yet if the query distribution is skewed, we should be able to get better expected case performance by adapting the samples to the distribution. In a recent paper, we accomplished this for a known query distribution. We described an efficient algorithm for selecting the optimal samples by reducing the problem to finding a minimum-weight k-link path in a directed acyclic graph. In our experiments with a real query distribution, using the optimal samples was up to 30 times faster than using the same number of samples at regular intervals. While there are some heuristics that improve the performance with an unknown query distribution, no satisfactory solution for dynamically adapting the samples exists so far.

Joint work with Paolo Ferragina and Rossano Venturini, University of Pisa, Italy

 

2012-10-03:

Author:

Francesc López, UPC Barcelona.

Where:

DII, Sala 33, 14:30-16:00.

Title:

Integrating network topology design and line frequency setting in semi-congested rapid transit systems.

Abstract:

In this second talk, I will focus on the solving techniques rather than the mathematical formulation of a model that integrates the network topology design (NTD) and line frequency setting (LFS) of an extension of a rapid transit system.

The NTD determines if the current set of working lines will be extended. If so, the layout of the new lines will be constructed by means of a set of candidate stations but without exceeding the available network infrastructure budget.

On the other hand, the LFS assigns vehicles, which are treated as discrete variables, and frequencies, which are considered as continuous variables, to the lines while meeting link and vehicle capacity constraints as well as the size of vehicle’s fleet and planning horizon requirements.

The model is formulated as a mixed integer linear programming problem and solved under a preliminary benders decomposition framework which is currently being extended in order to cope with some non-linearities due to the inclusion of passenger waiting time to board to a vehicle.

 

2012-09-26:

Author:

Marcos Goycoolea, UAI.

Where:

DII, Sala 33, 14:30-16:00

Title:

Decomposition methods and conic-programming.

Abstract:

Linear Programming (LP) has made great strides in recent decades. Both commercial and open-source black-box LP solvers are numerically robust, and can solve very large problems (1M+ variables) to optimality in just minutes. Moreover, for those problems that are too large for even today’s solvers, there are a number of decomposition methods, such as the Dantzig-Wolfe (DW) decomposition method, the Benders decomposition, Lagrangian Relaxation and others, that make solving such problems possible in important real-world applications.

Though Conic Programming (CP) has also made great strides, we are far behind in terms of robustness and in terms of the size of problems that can be solved.

Recently there have been some attempts to develop DW decomposition methods for CP. Unfortunately, there are a number of reasons why these methods have not been successful. Most importantly, DW is not guaranteed to converge in CP, and even when it does, it is known to have poor tail-off in the convergence.

In this talk I will describe a new column-generation decomposition method for CP inspired by the recent work of Bienstock and Zuckerberg for solving specially structured large-scale LPs. It is easy to see that this new method overcomes many of the limitations of DW. Preliminary computations are presented showing that in some SOCP problem instances we can significantly outperform state-of-the art methods.

Joint work with: Eduardo Moreno, Gonzalo Muñoz and Juan Pablo Vielma.

 

2012-09-12:

Author:

Maxim Sviridenko, Warwick, UK.

Where:

DII, Sala 33, 14:30-16:00

Title:

New Algorithms for the Minimum Set Cover and Related Problems.

Abstract:

We will start the talk with classical Minimum Set Cover Problem. There are two well-known approximability results for this problem. The results of Hochbaum and Even and Bar-Yehuda in the early 80’s show that one can get a k-approximation algorithm by using primal dual or local ratio algorithms. Chvatal (1979) shows that the greedy algorithm has performance guarantee ln(n) where k is maximal number of sets covering each element in the ground set and n is the total number of elements. Both algorithms are best possible under natural complexity assumptions. We design an algorithm with performance guarantee (k – 1)(1 – e- ln n∕(k-1)) + 1 which combines two classical bounds in one formula. Also in the regime when k = lnn we get a constant factor improvements over classical algorithms. We also discuss integrality gap and non-approximability of the set cover in this regime.

In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S1,…,Sm where each set Si ∈ 2[n] has a positive requirement ki that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets where the cover time is the first position in the order when ki elements of Si have a lower index. We give a 2-approximation for this preemptive version of the problem. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved 12.4-approximation for the non-preemptive problem improving recent results by Skutella, Williamson and Bansal, Gupta and Krishnaswamy.

Based on joint works with Sungjin Im (Duke), Rishi Saket (IBM), Ruben van der Zwaan (University of Maastricht)

 

2012-09-05:

Author:

Francesc López, UPC Barcelona.

Where:

DII, Sala 33, 14:30-16:00

Title:

Integrating network design and line frequency setting in semi-congested rapid transit systems

Abstract:

I will present a model for the network design and line frequency setting of an extension of a rapid transit system. The network design determines if the current set of working lines will be extended. If so, the new lines will be constructed by means of a set of candidate stations but without exceeding the available network infrastructure budget. On the other hand, the line frequency setting assigns vehicles, which are treated as a discrete variables, and frequencies to the lines while meeting link and vehicle capacity constraints as well as the size of vehicle’s fleet and planning horizon requirements. The model is formulated as a mixed integer linear programming problem and solved under a preliminary benders decomposition framework which is currently being extended in order to cope with passenger waiting time to board to a vehicle.

 

2012-08-29:

Author:

Fernando Krell, Columbia University.

Where:

Auditorio DCC, Blanco Encalada, tercer piso, 14:3-16:00.

Title:

Secure Computation in Sublinear (Amortized) Time.

Abstract:

Traditional approaches to generic secure computation begin by representing the function F being computed as a circuit. If F depends on each of its input bits, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for non-trivial functions since each party must “touch” every bit of their input lest information about the other party’s input be leaked. This seems to rule out many applications of secure computation (e.g., database search) in scenarios where inputs are huge.

Adapting and extending an idea of Ostrovsky and Shoup, we present an approach to secure two-party computation that yields protocols running in sublinear time, in an amortized sense, for functions that can be computed in sublinear time on a random-access machine (RAM). Moreover, each party is required to maintain state that is only (essentially) linear in its own input size. Our protocol applies generic secure two-party computation on top of oblivious RAM (ORAM). We present an optimized version of our protocol using Yao’s garbled-circuit approach and a recent ORAM construction of Shi et al.

We describe an implementation of this protocol, and evaluate its performance for the task of obliviously searching a database with over 1 million entries. Because of the cost of our basic steps, our solution is slower than Yao on small inputs. However, our implementation outperforms Yao already on DB sizes of 218 entries (a quite small DB by today’s standards).

To appear in CCS’12.

Join work with Dov Gordon, Jonathan Katz, Vlad Kolesnikov, Tal Malkin, Mariana Raykova, and Yevgeniy Vahlis.

 

2012-08-08:

Author:

Claudio Telha, Post-Doc Núcleo Milenio Información y Coordinación en Redes.

Where:

DII, Sala 33, 14:30-16:00.

Title:

El juego de las minorías.

Abstract:

Consideramos un juego de sobrevivencia que comienza con N jugadores, y se ejecuta por rondas hasta que el número de jugadores sea igual a 1 o 2. En cada ronda, los jugadores votan A o B. Aquellos jugadores que votan por la mayoría son eliminados. En la charla consideramos la siguiente pregunta: ¿Que tamaño mínimo debe tener una coalicion para garantizar que uno de sus miembros sobreviva hasta el final del juego, usando una estrategia adecuada?

 

2012-08-01:

Where:

Sala Seminario DIM, 14:30-16:00.

Author:

Martin Matamala, Universidad de Chile.

Titulo:

Injective coloring with arithmetic constraints.

Abstract:

An injective coloring of a graph is a vertex labeling such that two vertices sharing a common neighbor get different labels. In this work we introduce and study what we call colorings. These are injective colorings using positive integers such that the average of the colors assigned to two vertices is not the color of one of their common neighbors. The smallest integer k such that an injective (resp. additive) coloring of a given graph Gexists with k colors (resp. colors in {1,…,k}) is called the injective (resp. additive) chromatic number (resp. index). They are denoted by χi(G) and χ′a(G), respectively.

In the first part of this work, we present several upper bounds for the additive chromatic index. On one hand, we prove a super linear upper bound in terms of the injective chromatic number for arbitrary graphs, as well as a linear upper bound for bipartite graphs and trees. Complete graphs are extreme graphs for the super linear bound, while complete balanced bipartite graphs are extreme graphs for the linear bound. On the other hand, we prove a quadratic upper bound in terms of the maximum degree.

In the second part, we study the computational complexity of computing χ′a(G). We prove that it can be computed in polynomial time for trees. We also prove that for bounded treewidth graphs, to decide whether χ′a(G) ≤ k, for a fixed k, can be done in polynomial time. On the other hand, we show that for cubic graphs it is -complete to decide whether χ′a(G) ≤ 4. We also prove that for every ε > 0 there is a polynomial time approximation algorithm with approximation factor n1∕3+ε for χ′a(G), when restricted to split graphs. However, unless P =NP, for every ε > 0 there is no polynomial time approximation algorithm with approximation factor n1∕3-ε for χ′a(G), even when restricted to split graphs.

This is Joint Work with N. Astromujoff, M. Chapelle, I. Todinca, J. Zamora.

 

 

2012-07-25:

Author:

Nicolas Stier, Columbia Business School.

Where:

Sala Seminario DIM, 14:30-16:00.

Title:

The competitive facility location problem on a duopoly.

Abstract:

We consider a competitive facility location game on a network where consumers located on vertices wish to connect to the nearest facility. Knowing this, competitors place facilities on vertices to maximize market share. Focusing in the two-player case, we study conditions that guarantee the existence of pure-strategy Nash equilibria for progressively more complicated networks. The case of trees, which extends the classic Hotelling model, is well-studied: equilibria are characterized by centroids of the tree. We find that cycles admit equilibria when there are vertices with sufficiently big demands. For a general graph, we construct a tree of maximal bi-connected components and apply the results for trees and cycles to get sufficient conditions for equilibrium existence. This provides a complete and efficient characterization of equilibria for networks where the central bi-connected component is a vertex or a cycle. We quantify the maximum inefficiency of equilibria with bounds that depend on topological parameters of the network. These bounds rely on trees, which are worst instances because for these games removing an edge from a graph always increases consumer cost.

 

2012-07-18:

Author:

Robert Bixby, President and co-founder Gurobi.

Title:

Presolve for linear and mixed-integer programming.

Where:

Sala 33, DII, 14:30-16:00.

 

2012-07-11:

Author:

Flavio Guíñez, Universidad de Chile.

Where:

Sala 33, DII, 14:30-16:00.

Title:

An approach to the Wide Partition Conjecture using discrete tomography ideas.

Abstract:

Rotas basis conjecture states that for any matroid M of rank n and bases B1,…,Bn of M, there is a way of sorting the elements of the basis Bi in the i-th row of a n×n grid in such a way that the elements of every column also form a basis of M.

T. Chow and B. Taylor, as an attempt to prove this conjecture using an induction approach, studied a generalization of this problem in which the n × n grid is replacing for an arbitrary Young tableau, and each given basis for an independent set of the size of the length of the corresponding row of the tableau. Of course, this is in not true for every tableau, but they posed the so-called Wide Partition Conjecture (WPC) which tries to characterize the ones that satisfy this property. Unfortunately, the WPC seems to be hard even for free matroids, which for the n × n grid just corresponds to the (trivial) existence of Latin tableaux or order n. The WPC for free matroids is a beautiful combinatorial problem which has an extremely simple statement as you can check in Open Problem Garden site. http://garden.irmacs.sfu.ca/?q=op/wide_partition_conjecture.

This talk will provide an overview of the WPC for free matroids, as well as a nice approach to this conjecture using ideas from discrete tomography. I will also present some partial results that can be obtained using this approach, which could reduce the problem to the existence of integrality of an LP formulation that admits fractional solutions.

 

2012-07-04:

Author:

Vahab Mirrokni, Google Research.

Where:

Sala 33, DII, 14:30-16:00.

Title:

Online Stochastic Matching: Primal, Dual, and Simultaneous Approximations.

 

2012-06-27:

Author:

Jeremy Barbay, Universidad de Chile.

Where:

t.b.a., 14:30-16:00.

Title:

Prefix Free Codes in Linear Time.

Abstract:

Considering the computation of an optimal prefix-free code over n symbols from their frequencies {f1,…,fn} given in arbitrary order, we give a linear time algorithm in the word-RAM memory model and an (input order oblivious) instance optimal algorithm in the algebraic model. These complexities improve over both the traditional (nlog n) algorithm from Huffman and the (nk) adaptive algorithm from Belal and Elmasry, where kis the number of distinct code lengths in any optimal code.

 

2012-06-20:

Author:

Christopher Ryan, University of Chicago.

Where:

Sala 33, DII, 14:30-16:00.

Title:

Mechanism design with ordinal preferences.

Abstract:

We consider the implementability of social choice functions (allocation rules) based on ordinal preferences as opposed to declared utilities, which is standard in the literature. In our model, players are characterized by their preference level for each outcome. A pre-allocation rule associates an outcome to each preference level matrix (indexed by outcome and players). We characterize partial and full implementability of certain classes of pre-allocation rules using properties of cycles and strongly connected components in related networks.

This is joint work with Maurice Queyranne (CMM, Universidad de Chile and University of British Columbia) and Matthias Koeppe (UC Davis).

 

2012-06-13:

Author:

Adriana Piazza, Universidad Federico Santa María.

Where:

Sala 33, DII, 14:30-16:00.

Title:

Steady states of a forest plantation when carbon sequestration and economic benefits of timber are considered.

Abstract:

We try to characterize the steady states of a forest plantation when carbon sequestration and economic benefits of timber are considered. I will give conditions for the existence and uniqueness of the steady state in terms of the parameters of the model, only for the dual aged forest. We work now on the generalization of these results for a n-aged forest. This is a starting research project joint with Santanu Roy of the Department of Economics of SMU, Dallas.

 

2012-06-06:

Author:

Jeroen van de Graaf, Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Brasil.

Where:

Auditorio DCC, 14:30-16:00.

Title:

Internet Voting Protocols with Everlasting Privacy.

Abstract;

Many internet voting protocols with individual and universal verifiability, such as Helios, are based on homomorphic encryption. That is, they use an encryption algorithm with the following property: E(m1) ⋅ E(m2) =E(m1 + m2). Obviously, this property is useful to add encrypted votes. However, a drawback of these voting schemes is that if the encryption algorithm gets broken, 20 of 50 years from now, it is possible to violate the privacy of the votes cast. In this talk I will present a general improvement, showing how to encode votes with a homomorphic scheme that provides everlasting privacy. I will also outline how to apply this idea to mix-nets

 

2012-05-30:

Author:

Nicolas Figueroa, Universidad Católica de Chile.

Where:

Sala 33, DII, 14:30-16:00.

Title:

Implementability, revenue equivalence and graphs.

Abstract:

We will present some results where the implementability of a social choice function can be characterized through properties (no negative cycle, existence of a potential) in some graphs associated to the social choice function. Moreover we will characterize, in terms of the associated graph, under which conditions the environment satisfies the revenue equivalence property, which says basically that any implementation of a social choice function gives the same revenue to the principal.

 

2012-05-23:

Author:

Srinivas Sati Rao, University of Corea.

Where:

Auditorio DCC, 3er piso, 14:30-16:00.

Title:

Space Efficient Two Dimensional Range Minimum Data Structures.

Abstract:

The two dimensional range minimum query problem is to preprocess a static two dimensional array A, such that subsequent queries, asking for the position of the minimum element in a rectangular range within A, can be answered efficiently. In this talk, I will present some recent progress on this problem, describing various time-space trade-offs, between the space used to store the structure and the time required to answer a query, for this problem, considering two slightly different models called indexing and encoding models.

 

2012-05-16:

Author:

Jose Soto, Universidad de Chile.

Where:

Sala seminarios CMM (7mo piso), 14:30-16:00.

Title:

Vendedor viajero en grafos de Barnette y grafos cúbicos.

Abstract:

D.Barnette conjeturó en 1969 que todo grafo cúbico planar y bipartito (también llamados grafos de Barnette) es Hamiltoniano. No es difícil encontrar tours cerrados que visiten los n vértices de un grafo de Barnette, de largo 4n∕3. Sin embargo, no se conocían mejores cotas para el largo del tour. En el seminario, motivaré este problema y hablaré sobre un algoritmo de búsqueda local para encontrar tours de tamaño (4∕3-1∕18)n en un grafo de Barnette. Si queda tiempo, también daré una extensión que encuentra tours de tamaño (4∕3 – ε)n para cualquier grafo cúbico y 2-conexo.

Este es un trabajo en conjunto con Omar Larré y José Correa.

 

2012-05-09:

Author:

Roberto Cominetti, Universidad de Chile.

Where:

Sala 33 DII, 14:30-16:00

Title:

Estimación de sumas de Bernoullis.

 

2012-04-25:

Author:

Daniel Espinoza, Universidad de Chile.

Where:

Sala 33 DII, 14:30-16:00.

Title:

Extended formulations and the problem of finding minimal including/maximal included ellipsoids.

 

2012-04-18:

Author:

Nicolas Loira, Center for Genome Regulation, Universidad de Chile.

Where:

Sala 33 DII, 14:30-16:00.

Title:

Genomic-Scale Metabolic Models.

 

2012-04-11:

Author:

Yakov Nekrich, Universidad de Chile.

Where:

Auditorio DCC 3er piso, 14:30-16:00.

Title:

Efficient Range Reporting for Categorical Data.

Abstract:

In the colored (or categorical) range reporting problem the set of input points is partitioned into categories and stored in a data structure; a query asks for categories of points that belong to the query range. In this paper we study two-dimensional colored range reporting in the external memory model and present I/O-efficient data structures for this problem.

In particular, we describe data structures that answer three-sided colored reporting queries in O(K∕B) I/Os and two-dimensional colored reporting queries in O(log 2 log BN +K∕B) I/Os when points lie on an N × N grid, K is the number of reported colors, and B is the block size. The space usage of both data structures is close to optimal.

 

2012-04-04:

Author:

Jose Soto, Universidad de Chile.

Where:

Sala Seminarios CMM, 7mo Piso, 14:30-16:00.

Title:

Minimization of Symmetric Submodular Functions under Hereditary Constraints.

Abstract:

I will present a simple and efficient algorithm to find nonempty minimizers of a symmetric submodular function (SSF) over any family of sets closed under inclusion. Using this algorithm we can find, for instance, a minimum k-unbalanced cut of a graph; that is, a cut of minimum capacity for which one of the sides contains at most k vertices.

More generally, given a value oracle for a SSF, f, and a membership oracle for an hereditary family I, our algorithm reports all the inclusion-wise minimal nonempty minimizers of f in I using a cubic number of oracle calls.

Our algorithm is heavily based on Queyranne’s pendant-pair technique for minimizing unconstrained SSF.

This is joint work with M. Goemans

 

2012-03-28:

Author:

Robert Freund, Sloan School of Management, MIT.

Where:

Sala 33 DII, 14:30-16:00.

Title:

Implementation-Robust Design: Modeling, Theory, and Application to Photonic Crystal Design with Multiple and Combined Band Gaps.

Abstract:

We present a new theory for incorporating considerations of implementation into optimization models quite generally. It goes without saying that the computed solutions of many optimization problems cannot be implemented directly due to (i) the deliberate simplification of the model by ignoring integer/binary conditions that would otherwise render the problem intractable, (ii) human factors (we cannot convince others to do exactly what is prescribed in the computed solution), and/or (iii) technological reasons (we cannot be sure our plant or software can implement to the accuracy prescribed in the computed solution). We propose a new alternative paradigm for treating issues of implementation that we call implementation robustness. This paradigm is applied to the setting of optimizing the fabricable design of photonic crystals with large band-gaps. Such designs enable a wide variety of prescribed interaction with and control of mechanical and electromagnetic waves. We present and use an algorithm based on convex conic optimization to design fabricable two-dimensional photonic crystals with large absolute band gaps. Our modeling methodology yields a series of finite-dimensional eigenvalue optimization problems that are large-scale and non-convex, with low regularity and non-differentiable objective. By restricting to appropriate eigen-subspaces, we reduce the problem to a sequence of small-scale convex semidefinite programs (SDPs) for which modern SDP solvers can be efficiently applied. Among several illustrations we show that it is possible to design fabricable photonic crystals which exhibit multiple absolute band gaps for the combined transverse electric and magnetic modes. The optimized crystals show complicated patterns which are far different from existing photonic crystal designs. We employ subspace approximation and mesh adaptivity to enhance computational efficiency.

 

2012-03-21:

Author:

Jose Verschae, Universidad de Chile.

Where:

Sala 33 DII, 14:30-16:00.

Title:

A conjecture on online MSTs with recourse.

Abstract:

In the minimum spanning tree problem, we seek a minimum cost tree that connects all nodes in a graph. In the online setting, the nodes of a complete metric graph are revealed one be one in several iterations. In each iteration we seek to construct a spanning tree of low cost. If we are only allowed to extend the previous tree in each iteration – leaving the previous edges untouched – then the cost of the tree can be arbitrarily larger than the optimum of the current graph. More than 20 years ago, Imase and Waxman conjectured that touching a constant number of edges per iteration suffices to obtain close to optimal solutions. I will present an algorithm that we believe yields that result. I will show that this is indeed true if we assume a natural property on the sequence of optimal solutions. We conjecture that this property is true for every input.

This is joint work with N. Megow, M. Skutella and A. Wiese.

 

2012-01-11:

Author:

Dorit Hochbaum (USC)

Where:

Sala 33 DII, 14:15-15:15

Title:

Solving integer programming on monontone inequalities in poly time.

 

2012-01-04:

Author:

Mauricio Soto (U. de Orlans)

Where:

Sala seminarios DIM (5to piso) 14:15-15:15

Title:

On some topological properties of graphs and applications to Internet.

Abstract:

We first look how far from a tree a graph may be by the study of two parameters: hyperbolicity and treewidth. For hyperbolicity, we analyse the relation with others graph parameters, we also show that some graph decompositions allow its efficient computation. We compute both parameters on Internet snapshots at different levels of granularity and time periods. We propose some structural and algorithmic consequences of obtained values. Then, we study the graph clustering problem from the perspective of modularity, which measures a clustering quality and is largely studied in the literature. We analyse modularity from a theoretical point of view and describe its asymptotic behaviour for some graph families.