Seminars 2015

2015-30-12:

Author: Gonzalo Muñoz, Columbia U.

Where: Sala 33 DII.

When:  Wednesday, December 30, 14:30.

Title: Formulaciones lineales para problemas de optimización con tree-width acotado

Abstract:  Dado un problema de optimización, definimos su “grafo de intersección” como el grafo cuyos vértices están dados por las variables del problema, y que posee un arco por cada par de variables que aparecen en una misma restricción. Presentaremos formulaciones lineales de tamaño polinomial para cuando dicho grafo posea tree-width acotado (lo que implica baja densidad). Específicamente, para problemas binarios con n variables, tree-width w y restricciones dadas por oráculos, nuestra formulación tiene n*2^w variables y restricciones, y es exacta. Usaremos esta construcción para formular LPs de tamaño polinomial que pueden aproximar cualquier problema de optimización polinomial mixto (restricciones dadas por polinomios, y variables continuas y enteras) cuyo grafo de intersección tiene tree-width acotado. Esta aproximación satisface tolerancias de factibilidad y optimalidad arbitrariamente pequeñas.

2015-23-12:

Author: Cristóbal Guzmán, CWI, Amsterdam.

Where: Sala 33 DII.

When:  Wednesday, December 23, 14:30.

Title: Statistical Query Algorithms for Stochastic Convex Optimization

Abstract: We study the complexity of stochastic convex optimization given only statistical query (SQ) access to the objective function. In this model, instead of having access to i.i.d.samples of the underlying distribution an algorithm is only allowed to query bounded functions, and the oracle answers the expected value up to some tolerance. We show that well-known and popular methods, including first-order iterative methods and polynomial-time methods, can be implemented using only statistical queries. For many cases of interest we derive nearly matching upper and lower bounds on the estimation (sample) complexity including linear optimization in the most general setting. We then present several consequences for machine learning, differential privacy and proving concrete lower bounds on the power of convex optimization based methods. A new technical ingredient of our work is SQ algorithms for estimating the mean vector of a distribution over vectors in R^d with optimal estimation complexity. This is a natural problem and we show that our solutions can be used to get substantially improved SQ versions of Perceptron and other online algorithms for learning halfspaces.

This is joint work with Vitaly Feldman (IBM-Almaden) and Santosh Vempala (Georgia Tech).

2015-12-09:

Author: Qingxia Kong, UAI.

Where: Sala 33 DII.

When:  Wednesday, December 9, 14:30.

Title: Appointment Scheduling Under Schedule-Dependent Patient No-Show Behavior

Abstract: This paper studies an appointment scheduling problem under schedule-dependent patient no-show behavior. The problem is motivated by our studies of independent datasets from countries in two continents which identify a significant time-of-day effect on patient show-up probabilities. We deploy a distributionally robust model, which minimizes the worst case total expected cost of patient waiting and service provider’s idle and overtime, by optimizing the scheduled arrival times of patients. We show that this model under schedule-independent patient show-up behavior can be reformulated as a copositive program and then be approximated by semidefinite programs. These formulations are obtained by a new technique that uses a completely positive program to equivalently represent a linear program with uncertainties present in both the objective function and the right-hand side of the constraint sets. To tackle the case when patient no-shows are endogenous on the schedule, we construct a set of dual prices to guide the search for a good schedule and use the technique iteratively to obtain a near optimal solution. Our computational studies reveal a significant reduction in total expected cost by taking into account the time-of-day variation in patient show-up probabilities as opposed to ignoring it.

2015-12-02:

Author: Nicolas Figueroa, PUC.

Where: Sala 33 DII.

When:  Wednesday, December 2, 14:30.

Title: Selling to Buyers with Correlated Values

Abstract: In this talk, we will study the problem of selling objects to buyers who know information relevant to other buyers. By setting prices in the early stages, the seller controls the “beliefs-martingale” of future bayers, and therefore faces a tradeoff between rent extraction and future profits.

2015-11-25:

Author: Schroeder Marc, Maastricht U.

Where: Sala 33 DII.

When:  Wednesday, November 25, 14:30.

Title: Optimal price cap regulation in congested networks

Abstract: We study the effect of price caps on price competition between firms in network routing problems. Each firm owns a link in a congested network and sets a price so as to maximize profit. Acemoglu and Ozdaglar (2007) provide a characterization of the prices in the subgame perfect equilibrium of this game (also called oligopoly equilibrium), but the corresponding latency costs can be arbitrary higher than the optimal latency costs. We analyze the situation in which a government is able to set a price cap in order to regulate competition. On the one hand, setting a price cap of zero corresponds to a Wardrop equilbrium. On the other hand, setting a price cap of infinity corresponds to an oligopoly equilibrium. We prove that for a two-link network with affine latency functions the latency costs at the optimal price cap are at most 8/7 times the optimal latency costs. The ratio between the latency costs at the optimal price and the optimal latency costs can be arbitrary high for more general latency functions due to the non-existence of oligopoly equilibria.

2015-11-18:

Author: Cristobal Navarro, DCC U Chile.

Where: Sala 33 DII.

When:  Wednesday, November 18, 14:30.

Title: Parallel Family Trees for Transfer Matrices in the Potts Model

Abstract: The transfer matrix approach is a practical technique for computing the partition function Z of a planar strip lattice G(V,E) of width $m$, and study its phase transitions. In this work we present an algorithm that computes the transfer matrix of planar strip lattices in the Potts Model. The main contribution of this work is the reduction of the configuration space, from O(4^m) to O(3^m), by grouping elements of the configuration space as family trees. Computation of the transfer matrix is achieved in parallel with an efficiency of up to 90%.

2015-11-11:

Author:  Dieter Mitsche, Université de Nice Sophia-Antipolis.

Where: Sala Multimedia CMM, sexto piso, Torre Norte, Beauchef 851

When:  Wednesday, November 11, 14:30.

Title: Strong-majority bootstrap percolation on regular graphs with low dissemination threshold

Abstract: Consider the following model of strong-majority bootstrap percolation one aph. Let r be some positive integer, and p in [0,1]. Initially, every vertex is active with probability p, independently from all other vertices. Then, at every step of the process, each vertex v of degree deg(v) becomes active if at least (deg(v)+r)/2 of its neighbours are active. Given any arbitrarily small p>0 and any integer r, we construct a family of d=d(p,r)-regular graphs such that with high probability all vertices become active in the end. In particular, the case r=1 answers a question and disproves a conjecture of Rapaport, Suchan, Todinca, and Verstraete (Algorithmica, 2011).

Joint work with X. Perez-Gimenez and P. Pralat.

2015-11-04:

Author:  Allyx Fontaine, U Bristol.

Where: Sala 315 DCC, Beauchef 851 (Poniente), 3er piso.

When:  Wednesday, November 2, 14:30.

Title: The k-mismatch problem revisited.

Abstract: We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern and every pattern-length substring of a text, as long as that Hamming distance is at most k. Whenever the Hamming distance is greater than k, we simply output “No”. We give improved algorithms for this problem in both the standard offline setting and also as a streaming model.

2015-10-27:

Author: Amin Saberi, Stanford U.

Where: Sala Seminario DIM, Beauchef 851, 5to piso.

When: TUESDAY, October 27, 14:30.

Title: Spectral Graph Theory and Optimization

Abstract: I will discuss an open problem at the intersection of
spectral graph theory and optimization.

2015-10-21:

Author: Tito Homem-De-Mello, UAI.

Where: Sala 33, DII.

When: Wednesday, October 21, 14:30.

Title: Identifying essential scenarios in stochastic optimization problems

Abstract: Traditional stochastic optimization models seek to optimize the expected value of a function that depends on the decision variables and on the underlying random variables in the problem. Such a formulation presupposes the knowledge of the probability distributions of those random variables. In practice, however, such distributions are often unknown, so typically  they are approximated using the available data, for example by taking the empirical distributions. In this talk we discuss a model that provides such approximation  in a robust way. In the particular case of random variables with finite discrete distributions, we study how this robust approximation helps to identify scenarios that are in some sense “essential” to the problem. We present results for problems from the literature to illustrate the ideas.

2015-10-14:

Author: Christoph Dürr, Univ Paris 06, UMR 7606, LIP6.

Where: Sala 33, DII.

When: Wednesday, Octubre 14, 14:30.

Title: Online Algorithms for Multi-Level Aggregation

Abstract: In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T . A service is defined as a subtree X of T that contains its root. This subtree X services all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the cost of all service sub-trees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgement Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. In earlier literature, the waiting cost functions are often assumed to be linear; we denote this special case by MLAP-L. The model with deadlines, denoted MLAP-D, has also been studied. Our main result is an online algorithm with competitive ratio O(D^42^D), where D is the depth of T . This is the first non-trivial competi- tiveness bound on trees of depth three or more, not only for MLAP but also for MLAP-D and MLAP-L. Previously constant-competitive algorithms were known only for D = 1, 2. We then consider the restricted case of MLAP when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, that applies even to MLAP-D and MLAP-L. For MLAP-D, we give a matching upper bound.
In addition, we study the Single-Phase MLAP, a variant of MLAP in which all requests are revealed at time 0 and they expire at some time {\theta}, not known to the online algorithm. The Single- Phase MLAP is a crucial tool in lower-bound proofs for MLAP. For the Single-Phase MLAP we give an online algorithm with optimal competitive ratio 4.

Joint work with Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang, Pavel Veselý.

2015-10-07:

Author: Gustavo Angulo, PUC.

Where: Sala 33, DII.

When: Wednesday 07 Octubre, 14:30.

Title: On polytopes arising in row permutations of matrices

Abstract: Given a polytope P whose elements are m-by-n matrices, we consider the problem of describing another polytope Q obtained by permuting the rows of the elements of P. We argue that this problem and some variants are hard in general. We discuss the case where P contains all binary matrices with lexicographically ordered rows and therefore Q contains all binary matrices with different rows. Although both polytopes are tractable, a compact linear description of Q remains unknown.

2015-09-30:

Author: José Verschae, PUC.

Where: Sala 33, DII.

When: Wednesday 30 September, 14:30.

Title: Min-Sum Scheduling under precedence constraints

Abstract: In this talk I will introduce the generalized min-sum scheduling problem under precedence constraints. Then I will shortly sketch an  approximation algorithm based on Sidney’s decomposition. The core of the talk will be on a reduction to a very fundamental problem on a subset system whose approximability seems to be open.

This is joint work with Andreas Schulz.

2015-09-23:

Author: Ruben Hoeksma, U Chile, DII.

Where: Sala 33, DII.

When: Wednesday 23 September, 14:30.

Title: Optimal mechanism design for sequencing with incomplete information

Abstract: In this talk we study optimal mechanism design for sequencing jobs on a single processor. Each of the jobs has a cost for waiting (their weight) and a processing time. One or both of the parameters can be private to the job, in which case we assume public knowledge of priors for that data. We consider the following problem. Given the priors for the jobs’ private data, find a sequencing rule and payment scheme that are incentive compatible with respect to the Bayes-Nash equilibrium and minimize the total expected payment made to the jobs.

When only the weights are private information to the jobs, these mechanisms are easy to identify and we even have a closed formula for the optimal mechanism. The same as with many other optimal mechanism design settings, the question if optimal mechanisms can still be found in polynomial time in cases where the private information is multi-dimensional has been open for some time. We show that the optimal mechanism design for sequencing with both weight and processing time as private parameters can in fact be solved in polynomial time.

We consider this problem in two different settings. One in which jobs are allowed to report smaller than their true processing time (the 2D case) and one where they are not (the 1.5D case). For the 1.5D case we give a linear program which is of exponential size, but we show that it can be compactified to polynomial size. For the 2D case we show that the optimal mechanism has a closed formula, which is in fact very similar to the one-dimensional case.

This is joined work with Marc Uetz (University of Twente).

2015-09-09:

Author: Jim Luedtke, U Wisconsin-Madison (2015-2016 sabbatical at UAI and CMM)

Where: Sala Multimedia CMM, 6to piso Beauchef 851 Norte.

Title: Decomposition Algorithms for Two-Stage Chance-Constrained Stochastic Programs

Abstract:  We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. This problem class can be considered as generalizing both chance-constrained and traditional two-stage stochastic programs. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. A key question we will discuss in the seminar is what is an appropriate form of the objective function in such a model. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve this class of problems. Computational results on a chance-constrained resource planning problem indicate that our algorithms are highly effective in solving these problems compared to a mixed-integer programming reformulation and a naive decomposition method.

This is joint work with Simge Kucukyavuz and Xiao Liu of The Ohio State University.

2015-09-02:

Author: Kim-Manuel Klein, U Kiel

Where: Sala Multimedia CMM, 6to piso Beauchef 851 Norte.

Title: Bin Packing in FPT-time

Abstract:  Given the classical bin packing problem, where a set of items of d different item sizes has to be packed into unit sized bins. It was a long standing open question if there exist a polynomial time algorithm for the problem when d is constant and was recently solved by Goemans and Rothvoß. In this talk we present first ideas and evidence that the problem might actually be solvable in FPT-time.

2015-08-26:

Author: Jeremy Barbay, DCC, U Chile:

Where: Auditorio DCC, 3re piso del edificio Beauchef 851 Norte.

Title: Adaptive Computation of the Swap-Insert Correction Distance

Abstract:  The Swap-Insert Correction distance from a string $S$ of length $n$ to another string $L$ of length $m\geq n$ on the alphabet $[1..d]$ is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting $S$ into $L$. Contrarily to other correction distances, computing it is NP-Hard in the size $d$ of the alphabet. We describe an algorithm computing this distance in time within $O(d^2 nm g^{d-1})$, where there are $n_\alpha$ occurrences of $\alpha$ in $S$, $m_\alpha$ occurrences of $\alpha$ in $L$, and where $g=\max_{\alpha\in[1..d]} \min\{n_\alpha,m_\alpha-n_\alpha\}$ measures the difficulty of the instance. The difficulty $g$ is bounded by above by various terms, such as the length of the shortest string $S$, and by the maximum number of occurrences of a single character in $S$.  The latter bound yields a running time within $O(d(n+m)+(d/(d-1)^{d-2})\cdot n^{d}(m-n))$ in the worst case over instances of fixed lengths $n$ and $m$ for $S$ and $L$, which further simplifies to within $O(n^d(m-n)+m)$ when $d$ is fixed, the state of the art for this problem.  This illustrates how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.

2015-08-19:

Author: Jannik Matuschke, U Tor Vergata, Rome:

Where: Sala 33 DII.

Title: Perfect matchings and virtual private networks on a ring

Abstract:  We will discuss a simple conjecture regarding the existence of a perfect matching in a sequence of graphs that arises by successively replacing the incidence vector of each vertex by its complement. The conjecture is motivated by the design of virtual private networks where the underlying network topology is a ring.

2015-08-12:

Author: Alvaro Lorca, Georgia Tech:

Where: Sala 33 DII, 14:30-15:30.

Title: Multistage Adaptive Robust Optimization for the Unit Commitment Problem

Abstract:  Motivated by the increasing adoption of wind and solar power generation in power systems, we present a multistage adaptive robust optimization model for the unit commitment problem, considering uncertainty in nodal net electricity loads. The key aspect of the proposed model is that it takes into account the time causality of dispatch decisions as uncertain parameters are unfolded in the hour-to-hour operation of the power system. To deal with large-scale instances, we explore the idea of simplified affine policies and develop a solution method based on constraint generation. Computational experiments on a 2736-bus system demonstrate the effectiveness of the proposed algorithm in practice and that the proposed model can outperform deterministic and two-stage robust models in both operational costs and system reliability. This is joint work with Andy Sun, Eugene Litvinov and Tongxin Zheng.

2015-08-05:

Author: Diego Morán, Virginia Tech:

Where: Sala 33 DII, 14:30-15:30.

Title: On the polyhedrality of the t-branch closure.

Abstract:  In this talk we study properties of the t-branch split cuts introduced by Li and Richard (2008). A t-branch split cut is an inequality that is valid for the set obtained by removing from a polyhedron the union of t split sets. This notion is a generalization of split cuts (1-branch split cuts). Cook et al. (1990) showed that the split closure of a rational polyhedron is again a polyhedron and Dash et al (2013) showed that cross cuts (2-branch splits cuts) also yield closures that are rational polyhedra. We further extend these results and show that the t-branch split closure is a polyhedron for all t=1,2,…. This is joint work with Sanjeeb Dash and Oktay Günlük  (IBM Research).

2015-06-17:

Author: Mario Bravo, Universidad de Santiago de Chile:

Where: Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: The sharp constant of asymptotic regularity for the Krasnoselskii– Mann iteration is equal to 1/\sqrt{\pi}.

Abstract: One of the most studied methods to compute fixed points of a non-expansive map T:C \to C is the Krasnoselskii-Mann iteration

x_{n+1} = (1-\alpha_{n+1})x_n + \alpha_{n+1}Tx_n.

In this talk we will show how to use a recursive optimal transport scheme in order to obtain sharp estimates between the iterates of the method. This approach will allow us to show that for every non-expansive map $T$ and every normed space the following bound for the rate of convergence of the error residuals

|| x_n – Tx_n|| \leq \frac{1}{\sqrt{pi}} \frac{\diam(C)}{\sqrt{\sum_{i=1}^n \alpha_i(1-\alpha_i)}}

is sharp, settling a conjecture of Baillon and Bruck(1992). Part of the previous work on this subject originated from discussions held in the AGCO seminar.

This is joint work with Roberto Cominetti.

2015-06-10:

Author: Iván Rapaport, Universidad de Chile:

Where: Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: Solving the Induced Subgraph problem in the randomized multiparty simultaneous messages model

Abstract: We study the message size complexity of recognizing, under the broadcast congested clique model, whether a fixed graph H appears in a given graph G as a minor, as a subgraph or as an induced subgraph. The n nodes of the input graph G are the players, and each player only knows the identities of its immediate neighbors. We are mostly interested in the one-round, simultaneous setup where each player sends a message of size O(log n) to a referee that should be able then to determine whether H appears in G. We consider randomized protocols where the players have access to a common random sequence. We completely characterize which graphs H admit such a protocol.

Joint work with Jarkko Kari, Martin Matamala and Ville Salo

2015-06-03:

Author: Cristóbal Guzmán, Universidad de Chile:

Where: Sala John von Neumann, 7th floor, CMM, 14:30-15:30.

Title: Density of Geometric Packing: A Symmetry-Based Optimization Perspective.

Abstract: How much of space can be filled with pairwise non-overlapping copies of a given solid? This is one of the oldest problems in mathematics, intriguing since the times of Aristotle, and remaining remarkably elusive until present times. For example, the three-dimensional sphere packing problem (posed by Kepler in 1611) was only solved in 1998 by Ferguson and Hales.

In this talk, I will provide some historical and modern applications of geometric packing problems, and I will introduce a methodology to derive upper bounds on the maximal density of such packings. These upper bounds are obtained by an infinite dimensional linear program, which is not computationally tractable. However, this problem can be approximated by using tools from sums of squares relaxations and symmetry reduction (harmonic analysis and representation theory), leading to rigorous computational upper bounds on the density.

Time permitting, I will present ongoing work with Maria Dostert, Fernando de Oliveira Filho and Frank Vallentin on the density of translative packings of superspheres (a.k.a ell_p balls).

2015-05-27:

Author: Evdokia Nikolova, University of Texas at Austin:

Where: Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: Approximation Algorithms for Offline Risk-averse Combinatorial Optimization.

Abstract: We consider generic optimization problems that can be formulated as minimizing the cost of a feasible solution w.x over a combinatorial feasible set F ⊂ {0, 1}^n. For these problems we describe a framework of risk-averse stochastic problems where the cost vector W has independent random components, unknown at the time of solution. A natural and important objective that incorporates risk in this stochastic setting is to look for a feasible solution whose stochastic cost has a small tail or a small convex combination of mean and standard deviation. Our models can be equivalently reformulated as nonconvex programs for which no efficient algorithms are known.

We provide efficient general-purpose approximation algorithms. They use as a black-box (exact or approximate) the solution to the underlying deterministic problem and thus immediately apply to arbitrary combinatorial problems. For example, from an available approximation algorithm to the deterministic problem, we construct an approximation algorithm with almost the same approximation factor for the stochastic problem. The algorithms are based on a geometric analysis of the nonlinear level sets of the objective functions.

2015-05-20:

Author: Christopher​ Thraves, Universidad de Concepción:

Where: Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: Optimal Path Discovery Problem with Homogeneous Knowledge.

Abstract: The subject of this presentation will be the Optimal Path Discovery (OPD) problem. That is: given a complete graph G = (V,E), a function F : 2^E —> [0,\infty) that assigns a positive value to each sub set of E, two nodes s and t in V, and a positive hidden value f(e) for each edge e in E, discover a path P* between s and t that it optimizes the value of F(P*). The issue is that the edge values f(e) are hidden. Hence, any algorithm that aims to solve the problem needs to uncover the value of some edges to discover an optimal path. The goal then is to discover an optimal path by means of uncovering the least possible amount of edge values. This problem is an extension of the well known Shortest Path Discovery problem in which f(e) represents the length of e in E, and F(P) computes the length of P.

In this talk, we will present a study of the OPD problem in a setting in which homogeneous information with respect to the values f(e) is given beforehand. As a measure to evaluate the performance of an algorithm, we will see first the maximum number of queries asked by an algorithm in any instance of size |V| = n. We will see that this measure does not differentiate correctly algorithms according to their performance. Therefore, we will introduce the Query Ratio, the ratio between the number of uncovered edge values and the least number of edge values required to solve the problem, as a new measure to evaluate algorithms that solve the OPD problem. When an input of size |V| = n is considered, we will prove a lower bound of 1 + 4/n – 8/n^2 on the query ratio of any algorithm that solves the OPD problem. As well, we will present an algorithm that solves the problem and we will prove that its query ratio is equal to 2 – 1/(n-1).

Joint work with Olivier Brun and Josu Doncel.

2015-05-13:

Author: Tjark Vredeveld, Maastricht University:

Where:Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: Scheduling with state-dependent machine speeds.

Abstract: We study a preemptive single machine scheduling problem where the machine speed is externally given and depends on the number unfinished jobs. The objective is to minimize the sum of weighted completion times. When the order of job completions is known, we give an LP-formulation that finds the optimal value. Using this formulation, we can give some structural property on an optimal solution. Using this structural property, we can show that the problem is NP-hard in the general case, but can be solved in polynomial time in the case of unit weights or unit processing times. Moreover, we develop a greedy algorithm that finds an optimal schedule given the order in which the jobs complete.

Joint work with Veerle Timmermans.

2015-05-06:

Author: Hiệp Hàn, Universidad de Chile:

Where: Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: Spectral stability for the partition function and the number of biased independent sets.

Abstract: In this talk we shall discuss two problems concerning the number of independent sets in regular graphs.
The results of Kahn and Zhao show that among all d-regular graphs on n vertices, the graph consisting of disjoint copies of complete bipartite graphs maximizes the number of independent sets. In the first part we discuss a spectral stability phenomenon for this result. Further, we are interested in counting “biased” independent sets in regular bipartite graphs, i.e. independent sets which are essentially contained in one of the partition classes. This problem is related to the hard-core model and the Glauber dynamics from statistical physics.

2015-04-29:

Author:  José Aliste, Universidad Andrés Bello:

Where: Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: Distinguishing trees from their U-polynomial.

Abstract: Polynomial invariants play an important role in the study of graphs. Some well-known examples include the chromatic polynomial and the Tutte polynomial. In 1999, Noble and Welsh introduced the U-polynomial as the “mighty” polynomial invariant, since it includes many of well-known invariants. In this talk we will introduce the problem of distinguishing trees from their U-polynomial. We’ll briefly explain the equivalence of this problem with a conjecture of Stanley on the chromatic symmetric function. We’ll present also all known results in this problem including a solution of the problem of a special class of trees known as caterpillars.

Joint work with José Zamora (Universidad Andrés Bello)

2015-04-22:

Author:  Pierre Aboulker, Universidad Andrés Bello:

Where: Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: Lines, betweenness and metric spaces.

Abstract: A celebrated Theorem of de Bruijn and Erdos states that every
noncollinear set of n points in the plane determines at least n distinct
lines. Line uv in the plane consists of all points p such that:

- dist(p,u) + dist(u,v) = dist(p,v) (i.e. u is between p and v) or
- dist(u,p) + dist(p,v) = dist(u,v) (i.e. p is between u and v) or
- dist(u,v) + dist(v,p) = dist(u p) (i.e. v is between u and p).

With this definition of line uv in an arbitrary metric space (V, dist),
Chen and Chvatal conjectured that every metric space on n points, where
n is at least 2, has at least n distinct lines or a line that consists
of all n points. The talk will survey results supporting this conjecture
as well as some discussions around lines induced by a set of points
together with a betweenness relations. Most of the presented results can
be found in “Lines, betweenness and metric paces” (P.A., X. Chen, G.

2015-04-15:

Author:  Juan Peypouquet, Universidad Técnica Federico Santa María:

Where: Sala Multimedia CMM, 6th floor, 14:30-15:30.

Title: A dynamical approach to an inertial forward-backward algorithm for convex minimization.

Abstract:  We introduce a new class of forward-backward algorithms for structured convex minimization problems in Hilbert spaces. Our approach relies on the time discretization of a second-order differential system with two potentials and Hessian-driven damping. This system can be equivalently written as a first order-system in time and space, each of the two constitutive equations involving only one of the two potentials. Its time dicretization naturally leads to the introduction of forward-backward splitting algorithms with inertial features. Using a Liapunov analysis, we show the convergence of the algorithm under conditions improving the classical step size limitation. Then, we specialize our results to gradient-projection algorithms, and give some illustration to sparse signal recovery and feasibility problems.

2015-04-08:

Author:  Daniel Espinoza, DII, Universidad de Chile:

Where: Sala Multimedia DIM, 6th floor, 14:30-15:30.

Title: Dos problemas combinatoriales: LP preprocessing con precedence
constraints; Optimización combinatorial en familias de conjuntos

Abstract:   Pre Procesamiento, bound strengthening y fijacion de variables es una
de las tecnicas mas usadas en optimizacion lineal entera; el primer
problema se centra en como extender estas ideas a un setting mas
especifico; donde las restricciones siguen siendo lineales; pero donde
una estructura combinatorial mas fuerte es conocida; nuestro interes
particular es considerar problemas mixtos 0-1 con restricciones de
precedencias; pero tambien es de interes el caso de estructuras mas
generales como “conflict graphs”.
El segundo problema se trata de optimizar una funcion lineal cx con
x_i \in {0,1}, pero con la condicion adicional de que la solucion sea
parte de una familia de conjuntos de las partes de un conjunto base
cerrado bajo union. Este problema tiene solucion para algunos casos
particulares; pero sigue abierto en otros contextos.

2015-04-01:

Author:  Marcos Kiwi, DIM, Universidad de Chile:

Where: Sala Multimedia DIM, 6th floor, 14:30-15:30.

Title: Chasing Markov chains

Abstract:   I will briefly describe a framework due to Mahdian et al (ITCS’12) which
is motivated by applications that concern graphs and data sets that are
evolving and massive in nature. In this framework, a very large object
changes over time and an algorithm can only track
changes by explicitly probing the object. The motivation is to
capture the inherent tradeoff between the complexity of maintaining an
up-to-date view of the object and the quality of results computed with
the available view. Then, I will pose two questions and leave the rest
(hopefully most) of the hour open for discussions

2015-03-25:

Author:  Andrea Jiménez,  Universidad de Valparaíso:

Where: Sala 33 DII, 14:30-15:30.

Title: Partitions of edge sets into paths and cycles

Abstract:   An old conjecture of Gallai claims that the edge set of every connected graph on n vertices can be partitioned into (the ceiling of) n/2 paths. A closely related problem that has drew great interest is as follows: given a graph G and a family of graphs G, is there a partition of the edge set of G into copies of elements in G? In this talk, we discuss our contributions to these problems and state some open questions left by our work.

More specifically, in the first half of the talk, I show a characterization of the class of all triangle-free graphs with odd distance at least 3 that admit a partition of its edge set into paths and cycles of length at least 4. In the second half, we study sufficient conditions on 2k-regular graphs for the existence of partitions of the edge set into paths of length in {2k-1,2k,2k+1}.

The first half of this talk is a joint work with Yoshiko Wakabayashi
and the second half with Fabio Bótler.

2015-03-18:

Author:  Evdokia Nikolova,  The University of Texas at Austin, USA:

Where: Sala 33 DII, 14:30-15:30.

Title: The Burden of Risk Aversion in Mean-Risk Selfish Routing
Abstract:  Considering congestion games with uncertain delays, we compute the inefficiency introduced in network routing by risk-averse agents. At equilibrium, agents may select paths that do not minimize the expected latency so as to obtain lower variability. A social planner, who is likely to be more risk neutral than agents because it operates at a longer time-scale, quantifies social cost with the total expected delay along routes. From that perspective, agents may make suboptimal decisions that degrade long-term quality. We define the price of risk aversion (PRA) as the worst-case ratio of the social cost at a risk-averse Wardrop equilibrium to that where agents are risk-neutral. For networks with general delay functions and a single source-sink pair, we show that the PRA depends linearly on the agents’ risk tolerance and on the degree of variability present in the network. In contrast to the price of anarchy, in general the PRA increases when the network gets larger but it does not depend on the shape of the delay functions. To get this result we rely on a combinatorial proof that employs alternating paths that are reminiscent of those used in max-flow algorithms. For series-parallel (SP) graphs, the PRA becomes independent of the network topology and its size. As a result of independent interest, we prove that for SP networks with deterministic delays, Wardrop equilibria maximize the shortest-path objective among all feasible flows.

Joint work with Nicolas Stier-Moses

2015-03-11:

Author:  Chien-Chung Huang,  Chalmers University of Technology, Sweden.

Where: Sala 33 DII, 14:30-15:30.

Title: An improved approximation algorithm for the stable marriage problem with one-sided ties.
Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A union B, E) where each vertex u in A union B ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). A matching M is said to be stable if there is no edge (a,b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that computing a maximum size stable matching is APX-hard.

In this paper we first consider the case when the preference lists of vertices in A are strict while the preference lists of vertices in B may include ties. This case is also APX-hard and the current best approximation ratio known here is 25/17 (~ 1.4706) which relies on solving an LP. We improve this ratio to 22/15 (~ 1.4667) by a simple linear time algorithm.