Browsing by Author "762785e6-d5fa-416a-be1a-b5308204887d"

Now showing items 1-8 of 8

    • A (5/3 +)-Approximation for unsplittable flow on a path: Placing small tasks into boxes 
      Grandoni, Fabrizio; Wiese, Andreas; Mömke, Tobias; Zhou, Hang (Association for Computing Machinery, 2018)
      In the unsplittable flow on a path problem (UFP) we are given a path with edge capacities and a collection of tasks. Each task is characterized by a subpath, a profit, and a demand. Our goal is to compute a maximum ...
    • A generalized parallel task model for recurrent real-time processes 
      Bonifaci, Vincenzo; Wiese, Andreas; Baruah, Sanjoy K.; Marchetti-Spaccamela, Alberto; Stiller, Sebastian; Stougie, Leen (Association for Computing Machinery, 2019)
      A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed acyclic graph (DAG), a period, and a relative ...
    • Breaking symmetries to rescue sum of squares in the case of makespan scheduling 
      Verdugo, Víctor; Verschae, José; Wiese, Andreas (Springer, 2020)
      The sum of squares (SoS) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for which a constant number of rounds of this ...
    • Fixed-Parameter approximation schemes for weighted flowtime 
      Wiese, Andreas (Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018)
      Given a set of n jobs with integral release dates, processing times and weights, it is a natural and important scheduling problem to compute a schedule that minimizes the sum of the weighted flow times of the jobs. There ...
    • On the extension complexity of scheduling 
      Tiwary, Hans Raj; Verdugo, Víctor; Wiese, Andreas (Elsevier, 2020)
      We study the minimum makespan problem on identical machines in which we want to assign a set of n given jobs to m machines in order to minimize the maximum load over the machines. We prove upper and lower bounds for the ...
    • Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs 
      Pilipczuk, Michal; Van Leeuwen, Erik Jan; Wiese, Andreas (Springer, 2020)
    • 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 ...
    • 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. ...