Operations Research

Starting with 2012/13, the FPT field gained some momentum in the fields of routing and scheduling. Since 2016, the Russian Foundation for Basic Research (RFBR) is funding research project 16-31-60007 on parameterized algorithms for NP-hard routing and scheduling problems at Novosibirsk State University.

Below are works of general interest to FPT in operations research as well as specific works on routing and scheduling. Preliminary versions of some papers are available on arXiv.

  • R. Ganian, S. Ordyniak (2016): The Complexity Landscape of Decompositional Parameters for ILP. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)
  • S. Kratsch (2016): On polynomial kernels for sparse integer linear programs. J. Comput. Syst. Sci. 82(5): 758–766.
  • K. Jansen, S. Kratsch, D. Marx, I. Schlotter (2013): Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1): 39-49.
  • M. R. Fellows, H. Fernau (2011): Facility location problems: A parameterized view. Discrete Applied Mathematics 159(11): 1118-1130.

Scheduling

  • Lin Chen, Dániel Marx, Deshi Ye and Guochuan Zhang (2017). Parameterized and approximation results for scheduling with a low rank processing time matrix. In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS'17)
  • R. van Bevern, R. Bredereck, L. Bulteau, C. Komusiewicz, N. Talmon, G. J. Woeginger (2016): Precedence-constrained scheduling problems parameterized by partial order width. In Proceedings of the 9th International Conference on Discrete Optimization and Operations Research (DOOR'16)
  • R. van Bevern, R. Niedermeier, O. Suchy (2016): A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. Journal of Scheduling. In press.
  • R. van Bevern, A. V. Pyatkin (2016): Completing partial schedules for Open Shop with unit processing times and routing. In Proceedings of the 11th International Computer Science Symposium in Russia (CSR'16)
  • R. van Bevern, J. Chen, F. Hüffner, S. Kratsch, N. Talmon, G. Woeginger (2015): Approximability and parameterized complexity of multicover by c-intervals. Inf. Process. Lett. 115(10): 744-749
  • M. Mnich, A. Wiese (2015): Scheduling and fixed-parameter tractability. Mathematical Programming 154(1-2): 533-562 (2015)
  • R. van Bevern, M. Mnich, R. Niedermeier, M. Weller (2015): Interval scheduling and colorful independent sets. Journal of Scheduling, 18 (5), pp. 449-469.
  • D. Hermelin, J.-M. Kubitza, D. Shabtay, N. Talmon, and G. Woeginger (2015). Scheduling two competing agents when one agent has significantly fewer jobs. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC’15)
  • A. Kononov, S. Sevastyanov, M. Sviridenko (2012) A complete 4-parametric complexity classification of short shop scheduling problems. Journal of Scheduling 15(4):427—446
  • M. M. Halldorsson and R. K. Karlsson (2006). Strip graphs: Recognition and scheduling. In Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG’06), volume 4271 of LNCS, pages 137–146. Springer, 2006.
  • M. Cieliebak, T. Erlebach, F. Hennecke, B. Weber, and P. Widmayer (2004): Scheduling with release times and deadlines on a minimum number of machines. In Exploring new Frontiers of Theoretical Informatics, volume 155 of IFIP International Federation for Information Processing, pages 209–222.
  • M. R. Fellows and C. McCartin (2003). On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2):317–324
  • H. L. Bodlaender and M. R. Fellows (1995). W[2]-hardness of precedence constrained k-processor scheduling. Operations Research Letters, 18(2):93–97
  • H. L. Bodlaender and K. Jansen (1993). On the complexity of scheduling incompatible jobs with unit-times. In Proceedings of the Mathematical Foundations of Computer Science 1993, volume 711 of LNCS, pages 291-300.

Routing

There is a book chapter surveying the (parameterized) complexity of various vehicle routing problems for serving arcs.

  • R. van Bevern, R. Niedermeier, M. Sorge, M. Weller (2014): Complexity of arc routing problems. In: Arc Routing: Problems, Methods, and Applications. SIAM

Other work on arc routing:

  • R. van Bevern, C. Komusiewicz, M. Sorge (2017): A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: theory and experiments. Networks. In press.
  • G. Gutin, M. Jones, and M. Wahlström (2016): The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth. SIAM J. Discrete Math., 30(4): 2177–2205.
  • G. Gutin, M. Wahlström, and A. Yeo (2017): Rural Postman parameterized by the number of components of required edges. J. Comput. Syst. Sci. 83(1): 121—131.
  • G. Gutin, M. Jones, B. Sheng, and M. Wahlström (2014). Parameterized Directed k-Chinese Postman problem and k-Arc-Disjoint Cycles problem on Euler digraphs. In Proc. 40th WG. LNCS, vol. 8747, pp. 250—262.
  • G. Gutin, M. Jones, B. Sheng (2014): Parameterized complexity of the k-Arc Chinese Postman Problem. In: Proc. 22nd ESA. LNCS, vol. 8737, pp. 530—541.
  • G. Gutin, G. Muciaccia, A. Yeo (2013): Parameterized complexity of k-Chinese Postman Problem. Theor. Comput. Sci. 513, 124—128
  • F. Dorn, H. Moser, R. Niedermeier, M. Weller (2013): Efficient algorithms for Eulerian Extension and Rural Postman. SIAM J. Discrete Math. 27(1), 75—94
  • M. Sorge, R. van Bevern, R. Niedermeier, M. Weller (2012): A new view on Rural Postman based on Eulerian Extension and Matching. J. Discrete Alg. 16, 12—33
  • M. Sorge, R. van Bevern, R. Niedermeier, and M. Weller (2011). From few components to an Eulerian graph by adding arcs. In Proc. 37th WG, pages 307–318.

Work on "node" routing, when nodes instead of arcs have to be served (this list should be expanded by someone more into the TSP direction):

  • G. Gutin and V. Patel, Parameterized TSP (2016): Beating the Average. SIAM J. Discrete Math. 30(1), 220—238.
  • P. N. Klein, D. Marx (2014). A subexponential parameterized algorithm for Subset TSP on planar graphs. In Proc. 25th SODA, pages 1812-1830
  • H.-J. Böckenhauer, J. Hromkovic, J. Kneis, J.Kupke (2007): The Parameterized Approximability of TSP with Deadlines. Theory Comput. Syst. 41(3): 431-444
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License