Browsing by Author "Verdugo, Víctor"

Now showing items 1-4 of 4

    • Semidefinite and linear programming integrality gaps for scheduling identical machines 
      Kurpisz, Adam; Mastrolilli, Monaldo; Mathieu, Claire; Mömke, Tobias; Verdugo, Víctor; Wiese, Andreas (Springer Verlag, 2018)
      Sherali and Adams (SIAM J Discrete Math 3:411–430, 1990) and Lovász and Schrijver (SIAM J Optim 1:166–190, 1991) developed systematic procedures to construct the hierarchies of relaxations known as lift-and-project methods. ...
    • Split scheduling with uniform setup times 
      Schalekamp, Frans; Sitters, René; Ster, Suzanne van der; Stougie, Leen; Verdugo, Víctor; Zuylen, Anke van (Springer, 2015)
      We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time, however, on the ...
    • Strong algorithms for the ordinal matroid secretary problem 
      Soto San Martín, José Antonio; Turkieltaub, Abner; Verdugo, Víctor (Informs, 2021)
      In the ordinal matroid secretary problem (MSP), candidates do not reveal numerical weights, but the decision maker can still discern if a candidate is better than another. An algorithm alpha is probability-competitive if ...
    • Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines 
      Correa Haeussler, José; Marchetti Spaccamela, Alberto; Matuschke, Jannik; Stougie, Leen; Svensson, Ola; Verdugo, Víctor; Verschae Tannenbaum, José (Springer, 2015)
      We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, ...