Document Open Access Logo

Fixed-Parameter Approximation Schemes for Weighted Flowtime

Author Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.28.pdf
  • Filesize: 0.49 MB
  • 19 pages

Document Identifiers

Author Details

Andreas Wiese
  • Department of Industrial Engineering and Center for Mathematical Modeling, Universidad de Chile, Chile

Funding

  • Wiese, Andreas: This work was partially supported by the Millennium Nucleus Information and Coordination in Networks ICM/FIC RC130003 and the grant Fondecyt Regular 1170223.

Cite As Get BibTex

Andreas Wiese. Fixed-Parameter Approximation Schemes for Weighted Flowtime. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.28

Abstract

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 are strong lower bounds for the possible approximation ratios. In the non-preemptive case, even on a single machine the best known result is a O(sqrt{n})-approximation which is best possible. In the preemptive case on m identical machines there is a O(log min{n/m,P})-approximation (where P denotes the maximum job size) which is also best possible.
We study the problem in the parametrized setting where our parameter k is an upper bound on the maximum (integral) processing time and weight of a job, a standard parameter for scheduling problems. We present a (1+epsilon)-approximation algorithm for the preemptive and the non-preemptive case of minimizing weighted flow time on m machines with a running time of f(k,epsilon,m)* n^{O(1)}, i.e., our combined parameters are k,epsilon, and m. Key to our results is to distinguish time intervals according to whether in the optimal solution the pending jobs have large or small total weight. Depending on this we employ dynamic programming, linear programming, greedy routines, or combinations of the latter to compute the schedule for each respective interval.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Scheduling
  • fixed-parameter algorithms
  • approximation algorithms
  • approximation schemes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, and Maxim Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 32-44. IEEE, 1999. Google Scholar
  2. Yossi Azar and Noam Touitou. Improved online algorithm for weighted flow time. CoRR, abs/1712.10273, 2017. URL: http://arxiv.org/abs/1712.10273.
  3. Nikhil Bansal. Minimizing flow time on a constant number of machines with preemption. Oper. Res. Lett., 33(3):267-273, 2005. URL: http://dx.doi.org/10.1016/j.orl.2004.07.008.
  4. Nikhil Bansal and Kedar Dhamdhere. Minimizing weighted flow time. ACM Trans. Algorithms, 3(4), 2007. URL: http://dx.doi.org/10.1145/1290672.1290676.
  5. Nikhil Bansal and Kirk Pruhs. The geometry of scheduling. SIAM Journal on Computing, 43(5):1684-1698, 2014. Google Scholar
  6. Jatin Batra, Naveen Garg, and Amit Kumar. Constant factor approximation algorithm for weighted flow time on a single machine in pseudo-polynomial time. CoRR, abs/1802.07439, 2018. URL: http://arxiv.org/abs/1802.07439.
  7. Chandra Chekuri and Sanjeev Khanna. A ptas for minimizing weighted completion time on uniformly related machines. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, Automata, Languages and Programming, pages 848-861, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. Google Scholar
  8. Chandra Chekuri and Sanjeev Khanna. Approximation schemes for preemptive weighted flow time. In Proceedings of the thiry-fourth annual ACM Symposium on Theory of computing, pages 297-305. ACM, 2002. Google Scholar
  9. Chandra Chekuri, Sanjeev Khanna, and An Zhu. Algorithms for minimizing weighted flow time. In Proceedings of the thirty-third annual ACM Symposium on Theory of computing, pages 84-93. ACM, 2001. Google Scholar
  10. Leah Epstein and Asaf Levin. Minimum total weighted completion time: Faster approximation schemes. CoRR, abs/1404.1059, 2014. URL: http://arxiv.org/abs/1404.1059.
  11. Naveen Garg, Amit Kumar, and V. N. Muralidhara. Minimizing total flow-time: The unrelated case. In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC 2008), pages 424-435. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92182-0_39.
  12. Fabrizio Grandoni, Stefan Kratsch, and Andreas Wiese. Parameterized approximation schemes for independent set of rectangles and geometric knapsack, 2017. Unpublished. Google Scholar
  13. Hans Kellerer, Thomas Tautenhahn, and Gerhard Woeginger. Approximability and nonapproximability results for minimizing total flow time on a single machine. SIAM Journal on Computing, 28(4):1155-1166, 1999. Google Scholar
  14. Dusan Knop and Martin Koutecký. Scheduling meets n-fold integer programming. CoRR, abs/1603.02611, 2016. URL: http://arxiv.org/abs/1603.02611.
  15. Stefano Leonardi and Danny Raz. Approximating total flow time on parallel machines. In Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing, pages 110-119. ACM, 1997. Google Scholar
  16. Joseph Y-T. Leung. Handbook of scheduling: algorithms, models, and performance analysis. CRC Press, 2004. Google Scholar
  17. Dániel Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  18. Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Math. Program., 154(1-2):533-562, 2015. Google Scholar
  19. Andreas Wiese. A (1+epsilon)-approximation for unsplittable flow on a path in fixed-parameter running time. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pages 67:1-67:13, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact