We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time $s$ occurs. This problem $1|$s-batch$|\sum T_i$ is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.

We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time s occurs. This problem 1|s-batch | ∑Ti is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.

We consider, for a positive integer $k$, induced subgraphs in which each component has order at most $k$. Such a subgraph is said to be $k$-divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$-divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for $2$-coloring...

We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.

In the Shapley-Scarf economy each agent is endowed with one unit of an indivisible good (house) and wants to exchange it for another, possibly the most preferred one among the houses in the market. In this economy, core is always nonempty and a core allocation can be found by the famous Top Trading Cycles algorithm. Recently, a modification of this economy, containing Q >= 2 types of goods (say, houses and cars for Q=2) has been introduced. We show that if the number of agents is 2, a complete...

We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph, is, however,...

We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph, is, however,...

We introduce a type of isomorphism among strategic games that we call local isomorphism. Local isomorphisms is a weaker version of the notions of strong and weak game isomorphism introduced in [J. Gabarro, A. Garcia and M. Serna, Theor. Comput. Sci. 412 (2011) 6675–6695]. In a local isomorphism it is required to preserve, for any player, the player’s preferences on the sets of strategy profiles that differ only in the action selected by this player. We show that the game isomorphism problem for...

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $\#W\left[P\right]$, the parameterized analogue of $\#P$. We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

In this paper we study the parameterized complexity of approximating the parameterized counting problems contained in the class $\#W\left[P\right]$, the parameterized analogue of $\#P$. We prove a parameterized analogue of a famous theorem of Stockmeyer claiming that approximate counting belongs to the second level of the polynomial hierarchy.

We investigate the proof complexity, in (extensions of) resolution and in bounded arithmetic, of the weak pigeonhole principle and of the Ramsey theorem. In particular, we link the proof complexities of these two principles. Further we give lower bounds to the width of resolution proofs and to the size of (extensions of) tree-like resolution proofs of the Ramsey theorem. We establish a connection between provability of WPHP in fragments of bounded arithmetic and cryptographic assumptions (the existence...

We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The...

We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items — we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The...