Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs

We consider the problem of scheduling n jobs in batches on a single parallel-batching machine, where the jobs are partitioned into jobs families and the jobs in each family have the same due date. The objective is to minimize the weighted number of tardy jobs. We first devise an efficient pseudo-polynomial time and a fully polynomial time approximation scheme for the weighted problem. Then we present $O(n^2)$-time and $O(n\log n)$-time algorithms for the case where the jobs have the same weight and for the case where the jobs have the same processing time, respectively.     

Efficient algorithms for the round-trip 1-center and 1-median problems

This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset $A^i\subseteq A$ of depots that i can potentially select from and use. When $A^i=A$ for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an $O(mn\lg n)$-time algorithm. For the restricted 1-median problem, we give an $O(mn\lg (|A|/m)+n^2\lg n)$-time algorithm. For the unrestricted 1-median problem, we give an $O(mn+n^2\lg \lg n)$-time algorithm.     

State complexity of power

The number of states in a deterministic finite automaton (DFA) recognizing the language $L^k$, where $L$ is regular language recognized by an $n$-state DFA, and $k?2$ is a constant, is shown to be at most $n{2}^{(k?1)n}$ and at least $(n?k)2^{(k?1)(n?k)}$ in the worst case, for every $n>k$ and for every alphabet of at least six letters. Thus, the state complexity of $L^k$ is $\Theta \left(n{2}^{(k?1)n}\right)$. In the case $k=3$ the corresponding state complexity function for $L^3$ is determined as $\frac{6n?3}{8}{4}^n?(n?1)2^n?n$ with the lower bound witnessed by automata over a four-letter alphabet. The nondeterministic state complexity of $L^k$ is demonstrated to be $nk$. This bound is shown to be tight over a two-letter alphabet.     

On the applicability of Postʼs lattice

For decision problems $\Pi (B)$ defined over Boolean circuits using gates from a restricted set B only, we have $\Pi (B){?}_m^{{\mathrm{AC}}^0}\Pi (B^{\prime })$ for all finite sets B and $B^{\prime }$ of gates such that all gates from B can be computed by circuits over gates from $B^{\prime }$. In this note, we show that a weaker version of this statement holds for decision problems defined over Boolean formulae, namely that $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{\wedge ,\vee \})$ and $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{0,1\})$ for all finite sets B and $B^{\prime }$ of Boolean functions such that all $f\in B$ can be defined in $B^{\prime }$.