More Like this

1. Finite permutation resolutions

   https://doi.org/10.1215/00127094-2022-0041  

   Balmer, Paul; Gallauer, Martin (February 2023, Duke Mathematical Journal)
2. Local Frechet Permutation

   Perry, Jonathan; Raichel, Benjamin (July 2024, Proceedings 36th Canadian Conference on Computational Geometry)

   Nishat, Rahnuma Islam (Ed.)

   In this paper we consider computing the Fréchet distance between two curves where we are allowed to locally permute the vertices. Specifically, we limit each vertex to move at most k positions from where it started, and give fixed parameter tractable algorithms in this parameter k, whose running times match the standard Fréchet distance computation running time when k is a constant. Furthermore we also show that computing such a local permutation Fréchet distance is NP-hard when considering the weak Fréchet distance. 

   more » « less
3. Resolutions by permutation modules

   https://doi.org/10.1007/s00013-020-01493-w  

   Balmer, Paul; Benson, Dave (November 2020, Archiv der Mathematik)

   null (Ed.)
4. Bayesian Optimization over Permutation Spaces

   https://doi.org/10.1609/aaai.v36i6.20604  

   Deshwal, Aryan; Belakaria, Syrine; Doppa, Janardhan Rao; Kim, Dae Hyun (June 2022, Proceedings of the AAAI Conference on Artificial Intelligence)

   Optimizing expensive to evaluate black-box functions over an input space consisting of all permutations of d objects is an important problem with many real-world applications. For example, placement of functional blocks in hardware design to optimize performance via simulations. The overall goal is to minimize the number of function evaluations to find high-performing permutations. The key challenge in solving this problem using the Bayesian optimization (BO) framework is to trade-off the complexity of statistical model and tractability of acquisition function optimization. In this paper, we propose and evaluate two algorithms for BO over Permutation Spaces (BOPS). First, BOPS-T employs Gaussian process (GP) surrogate model with Kendall kernels and a Tractable acquisition function optimization approach to select the sequence of permutations for evaluation. Second, BOPS-H employs GP surrogate model with Mallow kernels and a Heuristic search approach to optimize the acquisition function. We theoretically analyze the performance of BOPS-T to show that their regret grows sub-linearly. Our experiments on multiple synthetic and real-world benchmarks show that both BOPS-T and BOPS-H perform better than the state-of-the-art BO algorithm for combinatorial spaces. To drive future research on this important problem, we make new resources and real-world benchmarks available to the community. 

   more » « less
5. Capacity of Noisy Permutation Channels

   https://doi.org/10.1109/TIT.2023.3247812  

   Tang, Jennifer; Polyanskiy, Yury (July 2023, IEEE Transactions on Information Theory)