International Journal of Foundations of Computer Science

We consider a game-theoretical problem called selfish 2-dimensional bin packing game, a generalization of the 1-dimensional case already treated in the literature. In this game, the items to be packed are rectangles, and the bins are unit squares. The game starts with a set of items arbitrarily packed in bins. The cost of an item is defined as the ratio between its area and the total occupied area of the respective bin. Each item is a selfish player that wants to minimize its cost. A migration of an item to another bin is allowed only when its cost is decreased. We show that this game always converges to a Nash equilibrium (a stable packing where no single item can decrease its cost by migrating to another bin). We show that the pure price of anarchy of this game is unbounded, so we address the particular case where all items are squares. We show that the pure price of anarchy of the selfish square packing game is at least $2.3634$ and at most $2.6875$. We also present analogous results for the strong Nash equilibrium (a stable packing where no nonempty set of items can simultaneously migrate to another common bin and decrease the cost of each item in the set). We show that the strong price of anarchy when all items are squares is at least $2.0747$ and at most $2.3605$.

The following problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remaining which fits in it when the bin arrives. The goal is to minimize the total size of all the bins used. Previously, a lower bound of $\frac{5}{4}$ on the competitive ratio of this problem was achieved using items of size $S$ and $2S-1$. For these item sizes and maximum bin size $M=4S-3$, we obtain asymptotically matching upper and lower bounds, which vary depending on the ratio of the number of small items to the number of large items.

We study double circulant LCD codes over ${\mathbb{Z}}_{p^2}$ for all odd primes $p,$ and self-dual double circulant codes over ${\mathbb{Z}}_{p^2}$ for primes $p\equiv 1(\mathrm{\text{mod}} 4)$. We derive exact enumeration formulae, and asymptotic lower bounds on the minimum distance of the $p$-ary images of these codes by the classical Gray maps.

Link residual closeness is a novel graph based network vulnerability parameter. In this model, nodes are perfectly reliable and the links fail independently of each other. In this paper, the behavior of composite network types to the failure of individual links are observed and analyzed via link residual closeness which provides a much fuller characterization of the network.

Time-varying coverage, namely sweep coverage is a recent development in the area of wireless sensor networks, where a few mobile sensors sweep or monitor a comparatively large number of locations periodically. In this article, we study barrier sweep coverage with mobile sensors where the barrier is considered as a finite length continuous curve on a plane. The coverage at every point on the curve is time-variant. We propose an optimal solution for sweep coverage of a finite length continuous curve. Usually, energy source of a mobile sensor is a battery with limited power, so energy restricted sweep coverage is a challenging problem for long running applications. We propose an energy-restricted sweep coverage problem where every mobile sensor must visit an energy source frequently to recharge or replace its battery. We propose a $\frac{13}{3}$-approximation algorithm for this problem. The proposed algorithm for multiple curves achieves the best possible approximation factor 2 for a special case. We propose a 5-approximation algorithm for the general problem. As an application of the barrier sweep coverage problem for a set of line segments, we formulate a data gathering problem. In this problem a set of mobile sensors is arbitrarily monitoring the line segments one for each. A set of data mules periodically collects the monitoring data from the set of mobile sensors. We prove that finding the minimum number of data mules to collect data periodically from every mobile sensor is NP-hard and propose a 3-approximation algorithm to solve it.

We prove that one can construct various kinds of automata over finite words for which some elementary properties are actually independent from strong set theories like $T_n=:ZFC$ $+$ “There exist (at least) $n$ inaccessible cardinals”, for integers $n\ge 0$. In particular, we prove independence results for languages of finite words generated by context-free grammars, or accepted by 2-tape or 1-counter automata. Moreover we get some independence results for weighted automata and for some related finitely generated subsemigroups of the set ${\mathbb{Z}}^{3\times 3}$ of 3-3 matrices with integer entries. Some of these latter results are independence results from the Peano axiomatic system PA.

In this paper, we present nonsingular permutation polynomials from nonsingular feedback shift registers and examine nonlinearity and algebraic degree of nonsingular polynomials of certain forms. The upper bound on the nonlinearity of nonsingular Boolean functions is investigated. We also present $n$-variable nonsingular Boolean functions with algebraic degree $n-1$ and highest possible nonlinearity for odd $n$.