Noticias en español
Load 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 MoreIn this apportionment lottery, the House always wins.
Abstract Apportionment is the problem of distributing h indivisible seats across states in proportion to the states’ populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett suggested to apportion seats in a randomized way such that each state receives exactly their proportional share qᵢ of seats in expectation (ex ante proportionality) and receives either ⌊qᵢ⌋ or ⌈qᵢ⌉ many seats ex post (quota). However, there is a vast space of randomized...
Read More