Sorting by Strip Swaps is NP-Hard
We show that \emph{Sorting by Strip Swaps} (SbSS) is NP-hard by a polynomial reduction of \emph{Block Sorting}. The key idea is a local gadget, a \emph{cage}, that replaces every decreasing adjacency $(a_i,a_{i+1})$ by a guarded triple $a_i,m_i,a_{i+1}$ enclosed by guards $L_i,U_i$, so the only decreasing adjacencies are the two inside the cage. Small \emph{hinge} gadgets couple adjacent cages that share an element and enforce that a strip swap that removes exactly two adjacencies corresponds bijectively to a block move that removes exactly one decreasing adjacency in the source permutation. This yields a clean equivalence between exact SbSS schedules and perfect block schedules, establishing NP-hardness.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nonparametric Pricing and Hedging of Volatility Swaps in Stochastic Volatility Models
In this paper the zero vanna implied volatility approximation for the price of freshly minted volatility swaps is generalised to seasoned volatility swaps. We also derive how volatility swaps can be hedged using a strip …
Sorting by Swaps with Noisy Comparisons
We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability $p<1/2$. We use this process as prototype for the behaviour of randomized, comparison-based optimizat…
Multi-asset Generalised Variance Swaps in Barndorff-Nielsen and Shephard model
This paper proposes swaps on two important new measures of generalized variance, namely the maximum eigenvalue and trace of the covariance matrix of the assets involved. We price these generalized variance swaps for Barn…
Stripe: Tensor Compilation via the Nested Polyhedral Model
Hardware architectures and machine learning (ML) libraries evolve rapidly. Traditional compilers often fail to generate high-performance code across the spectrum of new hardware offerings. To mitigate, engineers develop …
Code GenerationmodelMulti-strip observation scheduling problem for ac-tive-imaging agile earth observation satellites
Active-imaging agile earth observation satellite (AI-AEOS) is a new generation agile earth observation satellite (AEOS). With renewed capabilities in observation and active im-aging, AI-AEOS improves upon the observation…
Earth ObservationScheduling