Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-095 | 9th October 2009 21:26

STRIP EXCHANGING IS HARD

RSS-Feed




Revision #1
Authors: Swapnoneel Roy
Accepted on: 9th October 2009 21:26
Downloads: 1373
Keywords: 


Abstract:

The sorting by strip exchanges (aka strip exchanging) problem is motivated by applications in optical character recognition and genome rearrangement analysis. While a couple of approximation algorithms have been designed for the problem, nothing has been known about its computational hardness till date. In this work, we show that the decision version of strip exchanging is NP-Complete. We present a few new lower bounds for the problem along with the stated result. The
NP-Completeness proof is based on reducing sorting by strip moves, an already known NP-Complete problem, to strip exchanging. The former is a widely studied problem also motivated by optical character recognition
and genome rearrangement analysis.



Changes to previous version:

1. "Department of Computer Science and Engineering" added to affiliation.

2. "Research supported in part by NSF grant CCF-0844796" added as a footnote.


Paper:

TR09-095 | 25th September 2009 17:58

STRIP EXCHANGING IS HARD





TR09-095
Authors: Swapnoneel Roy
Publication: 9th October 2009 21:00
Downloads: 1328
Keywords: 


Abstract:

The sorting by strip exchanges (aka strip exchanging) problem is motivated by applications in optical character recognition and genome rearrangement analysis. While a couple of approximation algorithms have been designed for the problem, nothing has been known about its computational hardness till date. In this work, we show that the decision version of strip exchanging is NP-Complete. We present a few new lower bounds for the problem along with the stated result. The
NP-Completeness proof is based on reducing sorting by strip moves, an already known NP-Complete problem, to strip exchanging. The former is a widely studied problem also motivated by optical character recognition
and genome rearrangement analysis.



ISSN 1433-8092 | Imprint