Combinatorial Filter Reduction: Special Cases, Approximation, and Fixed-Parameter Tractability

Fatemeh Zahra Saberifar, Ali Mohades, Mohammadreza Razzazi, Jason M. O'Kane
Journal of Computer and System Sciences
vol. 85
pp. 74–92
May 2017

Abstract Recent research in algorithmic robotics considers \emph{combinatorial filters}, which concisely capture the discrete structure underlying many reasoning problems for robots. An important recent result is that the filter minimization problem–-Given a filter, find the smallest equivalent filter–-is NP-hard. This paper extends that result along several dimensions, including hardness proofs for some natural special cases and for approximation, and new results analyzing the only known algorithm for this problem. We show that this problem is not fixed-parameter tractable for any of the obvious parameters, but it is fixed-parameter tractable for the combination of new parameters.

@article{SabMoh+17,
  author = {Fatemeh Zahra Saberifar and Ali Mohades and Mohammadreza Razzazi and
            Jason M. O'Kane},
  journal = {Journal of Computer and System Sciences},
  month = {May},
  pages = {74--92},
  title = {Combinatorial Filter Reduction: {S}pecial Cases, Approximation, and
           Fixed-Parameter Tractability},
  volume = {85},
  year = {2017}
}


O'Kane's home page
O'Kane's publication list

Last updated 2020-09-23.