Design of Efficient Polynomial Time Approximation Schemes for Scheduling and Related Optimization Problems

• Applicant: Professor Dr. Klaus Jansen
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 183875639

• Final Report Year: 2017

Final Report Abstract

No abstract available

Publications

• „A Faster FPTAS for the Unbounded Knapsack Problem“. In: Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers. 2015, S. 274–286
  K. Jansen und S. E. J. Kraft
  (See online at https://doi.org/10.1007/978-3-319-29516-9_23)
• „Fully Dynamic Bin Packing Revisited“. In: 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 2015, S. 135–151
  S. Berndt, K. Jansen und K.-M. Klein
  (See online at https://doi.org/10.1007/s10107-018-1325-x)
• „A PTAS for Scheduling Unrelated Machines of Few Different Types“. In: SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 23-28, 2016, Proceedings. 2016, S. 290–301
  J. C. Gehrke, K. Jansen, S. E. J. Kraft und J. Schikowski
  (See online at https://doi.org/10.1007/978-3-662-49192-8_24)
• „Approximation schemes for machine scheduling with resource (in-)dependent processing times“. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. 2016, S. 1526–1542
  K. Jansen, M. Maack und M. Rau
  (See online at https://doi.org/10.1137/1.9781611974331.ch104)
• „Closing the Gap for Makespan Scheduling via Sparsification Techniques“. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. 2016, 72:1–72:13
  K. Jansen, K. Klein und J. Verschae
  (See online at https://dx.doi.org/10.4230/LIPIcs.ICALP.2016.72)
• „About the Structure of the Integer Cone and its Application to Bin Packing“. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. 2017, S. 1571–1581
  K. Jansen und K. Klein
  (See online at https://doi.org/10.1137/1.9781611974782.103)