Catálogo de publicaciones - libros

We establish the following complexity results for prefix Gröbner bases in free monoid rings: 1. reduction steps are sufficient to normalize a given polynomial w.r.t. a given right-normalized system of prefix rules compatible with some total admissible wellfounded ordering >. 2. basic steps are sufficient to transform a given terminating system of prefix rules into an equivalent right-normalized system. 3. basic steps are sufficient to decide whether or not a given terminating system of prefix rules is a prefix Gröbner basis. The latter result answers an open question posed by Zeckzer in [10].

Motivated from recent applications in community TV networks and VLSI circuit design, we study variants of the classic bin packing problem, in which a set of items needs to be packed in a minimum number of unit-sized bins, allowing items to be . This can potentially reduce the total number of bins used, however, item fragmentation does not come for free. In , there is a bound on the total number of fragmented items. In , fragmenting an item increases the input size (due to a header/footer of fixed size that is added to each fragment). Both BP-SPF and BP-SIF do not belong to the class of problems that admit a .

In this paper, we develop fast for both problems. The running times of our schemes are in the input size. As special cases, our schemes yield AFPTASs for classical bin packing and for variable-sized bin packing, whose running times improve the best known running times for these problems.

The Boolean network (BN) is a mathematical model of genetic networks. It is known that detecting a singleton attractor, which is also called a fixed point, is NP-hard even for AND/OR BNs (i.e., BNs consisting of AND/OR nodes), where singleton attractors correspond to steady states. Though a naive algorithm can detect a singleton attractor for an AND/OR BN in ( 2) time, no ((2 − )) (> 0) time algorithm was known even for an AND/OR BN with non-restricted indegree, where is the number of nodes in a BN. In this paper, we present an (1.787) time algorithm for detecting a singleton attractor of a given AND/OR BN, along with related results.