Mariia Anapolska

Multithread Interval Scheduling with Flexible Machine Availabilities: Complexity and Efficient Algorithms

  • Mariia Anapolska
  • Christina Büsing
  • Tabea Brandt
  • Tobias Mömke
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , ,

    In the known Interval Scheduling problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specic time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We … Read more

    Efficient Algorithms for Multi-Threaded Interval Scheduling with Machine Availabilities

  • Mariia Anapolska
  • Christina Büsing
  • Tabea Brandt
  • Tobias Mömke
    • Categories Scheduling Tags ,

    In the known Interval Scheduling Problem with Machine Availabilities (ISMA), each machine has a contiguous availability interval and each job has a specific time interval which has to be scheduled. The objective is to schedule all jobs such that the machines’ availability intervals are respected or to decide that there exists no such schedule. We … Read more

    Minimum Color-Degree Perfect b -Matchings

  • Mariia Anapolska
  • Christina Büsing
  • Martin Comis
  • Tabea Brandt
    • Categories Dynamic Programming, Graphs and Matroids Tags , , , , ,

    The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a … Read more