ﻻ يوجد ملخص باللغة العربية
In this paper we study several variations of the emph{pancake flipping problem}, which is also well known as the problem of emph{sorting by prefix reversals}. We consider the variations in the sorting process by adding with prefix reversals other similar operations such as prefix transpositions and prefix transreversals. These type of sorting problems have applications in interconnection networks and computational biology. We first study the problem of sorting unsigned permutations by prefix reversals and prefix transpositions and present a 3-approximation algorithm for this problem. Then we give a 2-approximation algorithm for sorting by prefix reversals and prefix transreversals. We also provide a 3-approximation algorithm for sorting by prefix reversals and prefix transpositions where the operations are always applied at the unsorted suffix of the permutation. We further analyze the problem in more practical way and show quantitatively how approximation ratios of our algorithms improve with the increase of number of prefix reversals applied by optimal algorithms. Finally, we present experimental results to support our analysis.
Freight carriers rely on tactical plans to satisfy demand in a cost-effective way. For computational tractability in real large-scale settings, such plans are typically computed by solving deterministic and cyclic formulations. An important input is
In the graph balancing problem the goal is to orient a weighted undirected graph to minimize the maximum weighted in-degree. This special case of makespan minimization is NP-hard to approximate to a factor better than 3/2 even when there are only two
We show how to exploit excitable regimes mediated by localized structures (LS) to perform AND, OR, and NOT logical operations providing full logical functionality. Our scheme is general and can be implemented in any physical system displaying LS. In
Two-stage optimization with recourse model is an important and widely used model, which has been studied extensively these years. In this article, we will look at a new variant of it, called the two-stage optimization with recourse and revocation mod
Alice seeks an information-theoretically secure source of private random data. Unfortunately, she lacks a personal source and must use remote sources controlled by other parties. Alice wants to simulate a coin flip of specified bias $alpha$, as a fun