46 citations · 60 across the 13 of their papers we have counts for
12 papers · 1 filter
The k-Sum Lateness Problem on a Single Machine
Ricardo Arancibia-Castillo, José A. Soto
We study a single-machine scheduling problem in which each job has a nonnegative processing time and a due date . For a non-idling schedule , le…
Approximation Algorithms for Vertex-Connectivity Augmentation on the Cycle
Waldo Gálvez, Francisco Sanhueza-Matamala, José A. Soto
Given a -vertex-connected graph and a set of extra edges (links), the goal of the -vertex-connectivity augmentation problem is to find a set of minim…
The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
José Correa, Andrés Cristi, Boris Epstein +1
The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a varian…
The minimum cost query problem on matroids with uncertainty areas
Arturo I. Merino, José A. Soto
We study the minimum weight basis problem on matroid when elements' weights are uncertain. For each element we only know a set of possible values (an uncertainty area) that contain…
Strong Algorithms for the Ordinal Matroid Secretary Problem
José A. Soto, Abner Turkieltaub, Victor Verdugo
In the ordinal Matroid Secretary Problem (MSP), elements from a weighted matroid are presented in random order to an algorithm that must incrementally select a large weight indepen…
Symmetry exploitation for Online Machine Covering with Bounded Migration
Waldo Gálvez, José A. Soto, José Verschae
Online models that allow recourse are highly effective in situations where classical models are too pessimistic. One such problem is the online machine covering problem on identica…