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

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