Browsing by Subject "QPTAS"

Now showing items 1-2 of 2

    • A QPTAS for the general scheduling problem with identical release dates 
      Antoniadis, Antonios; Hoeksma, Rubén; Meißner, Julie; Verschae, José; Wiese, Andreas (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)
      The General Scheduling Problem (GSP) generalizes scheduling problems with sum of cost objectives such as weighted flow time and weighted tardiness. Given a set of jobs with processing times, release dates, and job dependent ...
    • Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs 
      Pilipczuk, Michał; Van Leeuwen, Erik; Wiese, Andreas (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018)
      We consider two optimization problems in planar graphs. In Maximum Weight Independent Set of Objects we are given a graph G and a family D of objects, each being a connected subgraph of G with a prescribed weight, and the ...