Noticias en español
Two-Edge Connectivity via Pac-Man Gluing.
Abstract: We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph $G$, compute a connected subgraph $H$ of $G$ with the minimum number of edges such that $H$ is spanning, i.e., $V(H) = V(G)$, and $H$ is 2-edge-connected, i.e., $H$ remains connected upon the deletion of any single edge, if such an $H$ exists. The $2$-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time $(\frac 5 4 + \varepsilon)$-approximation for the problem for an arbitrarily small $\varepsilon>0$, improving the previous best approximation ratio of...
Read MoreInverse and reverse optimization problems.
Abstract: nverse and reverse optimization problems aim to adjust the objective function of an underlying optimization problem while minimizing the extent of modification. In inverse optimization, the goal is to modify the objective function so that a given feasible solution becomes optimal. In reverse optimization, the goal is to modify the objective function so that the optimum value attains a specified number. In this talk, we mainly focus on inverse maximum-capacity optimization problems under the bottleneck Hamming distance, the weighted infinity norm and weighted span objectives. Our...
Read MoreDeterministic and stochastic fixed-point iterations in normed spaces.
Abstract: In this talk, we present a survey of techniques and results on error bounds and convergence rates for both deterministic and stochastic fixed-point iterations, with a focus on methods such as the Krasnoselskii-Mann and Halpern iterations. Our primary emphasis is on general normed spaces, where we employ tools from optimal transport to derive tight error bounds. For spaces with additional structure, such as Hilbert spaces, we also discuss existing techniques and the sharp results established in the literature. Finally, we highlight applications of these findings in reinforcement...
Read MoreSome dynamical invariants under strong orbit equivalence.
Abstract: A dynamical system is usually made up of a state space and a rule (a map acting on the space) that tells us how the system evolves over time. One of the central questions in studying these systems is figuring out when two of them are essentially the same, or conjugate, as we usually say. There are several known features, called invariants, that stay the same under conjugacy, but so far, no single invariant can completely characterize when two systems are conjugate. Because of that, it is natural to look at a slightly weaker idea of equivalence, called strong orbit equivalence. All...
Read MoreStochastic Halpern iteration in normed spaces and applications to reinforcement learning.
In this seminar, I will present recent results on the oracle complexity of the stochastic Halpern iteration with minibatching, a method designed to approximate fixed points of nonexpansive and contractive operators in finite-dimensional normed spaces. Under the assumption of uniformly bounded variance from the stochastic oracle, we show that the method achieves an oracle complexity of $\tilde{O}(\varepsilon^{-5})$ to obtain an $\varepsilon$-accurate expected fixed-point residual for nonexpansive operators. This improves upon previously known rates for the stochastic Krasnoselskii-Mann...
Read MoreDeterministic Impartial Selection with Weights.
Abstract: In the impartial selection problem, a subset of agents up to a fixed size k among a group of n is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is \alpha-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of \alpha of the votes received by the subset of size k with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted...
Read More