Noticias en español
A Unified Framework for Symmetry Handling.
Abstract: Discrete optimization problems are often solved using constraint programming or mided-integer programming techniques, using enumeration or branch-and-bound techniques. It is well known that if the problem formulation is very symmetric, there may exist many symmetrically equivalent solutions to the problem. Without handling the symmetries, traditional solving methods have have to check many symmetric parts of the solution space, which comes at a high computational cost. Handling symmetries in optimization problems is thus essential for devising efficient solution methods. In this...
Read MoreLoad Balancing Algorithms on Scheduling Problems with a Concave Function of the Load.
Abstract: In load balancing scheduling problems n jobs are to be assigned to m machines. Each job has its own processing time, and we define the load of a machine as the sum of the processing time of all jobs assigned to it. In this work, the machines have a concave non-decreasing function (accessed through a value oracle) applied to their loads and our goal is to maximize the sum of these valuations. This setting models a productivity maximization of machines where we aim to allocate indivisible resources, such as fuel tanks. We prove the existence of a PTAS for the offline version, which...
Read MoreConstructing separating hyperplanes for non-convex quadratic problem.
Abstract: In 1971, Balas introduced the intersection cut framework as a method for generating separating hyperplanes (or “cuts”) in integer optimization. These cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest intersection cuts. When S is a lattice, maximal S-free sets are well-studied from theoretical and computational standpoints. In this talk, we focus on the case when S is defined by a non-convex quadratic inequality and show how to construct basic maximal quadratic-free sets. Additionally, we explore how to generalize the...
Read MoreSelection and Ordering Policies for Hiring Pipelines via Linear Programming.
Abstract: Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions must be interviewed or made offers to. There is a finite time budget for interviewing or making offers, and a stochastic realization after each decision, leading to computationally-challenging problems. In the first problem, we study sequential interviewing and show that a computationally-tractable, non-adaptive policy that must make offers immediately after interviewing is near-optimal, assuming offerees always accept their offers. In the second problem,...
Read MoreWeak Ergodicity Approach to POMDPs.
Abstract: This seminar introduces Partially Observable Markov Decision Processes (POMDPs), emphasizing their relationship with decision problems and decidability. We then explore a novel theoretical class of POMDPs based on a weak ergodicity property. The seminar concludes by identifying necessary conditions for POMDPs to exhibit this characteristic, bridging the gap between this theoretical result and its potential practical implementation.
Read MoreEnergy-Efficient Distributed Algorithms for Synchronous Networks.
Abstract: We study the design of energy-efficient algorithms for well known distributed models of computation: the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or over all the nodes, of the number of rounds at which an edge, or a node, is activein the algorithm. We first show that every Turing-computable problem has a CONGEST algorithm with constant node-activation complexity, and therefore constant edge-activation complexity as well. That is, every node (resp., edge) is active in sending (resp., transmitting) messages...
Read More