The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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 ,
the parameterized analogue of . 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 ,
the parameterized analogue of . 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...
The MATRIX PACKING DOWN problem asks to find a row permutation of
a given (0,1)-matrix in such a way that the total sum of the first
non-zero column indexes is maximized. We study the computational
complexity of this problem. We prove that the MATRIX PACKING DOWN
problem is NP-complete even when restricted to zero trace symmetric
(0,1)-matrices or to (0,1)-matrices with at most two 1's per
column. Also, as intermediate results, we introduce several new simple
graph layout problems which...
Bref survol du théorème de non-plongement de J. Cheeger et B. Kleiner pour le groupe d’Heisenberg dans .
We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class of all -padded sets, if it is a subset of ). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties of a...
For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of , where is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to . To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which...
For both the edge deletion heuristic and the
maximum-degree greedy heuristic, we study
the problem of recognizing those graphs for which
that heuristic can approximate
the size of a minimum vertex cover within a constant factor
of r, where r is a fixed rational number.
Our main results are
that these problems are complete for the class of problems solvable via
parallel access to NP.
To achieve these main results, we also show that
the restriction of the vertex cover problem to those...
In this paper, we study the problem of makespan minimization for the multiprocessor
scheduling problem in the presence of communication delays. The communication delay
between two tasks i and j depends on the distance
between the two processors on which these two tasks are executed. Lahlou shows that a
simple polynomial-time algorithm exists when the length of the schedule is at most two
(the problem becomes 𝒩𝒫-complete when the length of the schedule
...
In this paper, we study the problem of makespan minimization for the multiprocessor
scheduling problem in the presence of communication delays. The communication delay
between two tasks i and j depends on the distance
between the two processors on which these two tasks are executed. Lahlou shows that a
simple polynomial-time algorithm exists when the length of the schedule is at most two
(the problem becomes 𝒩𝒫-complete when the length of the schedule
...
We consider μ-calculus formulas in a normal form: after a prefix of fixed-point quantifiers follows a quantifier-free expression. We are interested in the problem of evaluating (model checking) such formulas in a powerset lattice. We assume that the quantifier-free part of the expression can be any monotone function given by a black-box – we may only ask for its value for given arguments. As a first result we prove that when the lattice is fixed, the problem becomes polynomial (the assumption about...
In this paper we analyze some intrusion detection strategies
proposed in the literature and we show that they represent the
various facets of a well known formal languages problem: computing
the distance between a string x and a language L. In
particular, the main differences among the various approaches
adopted for building intrusion detection systems can be reduced to
the characteristics of the language L and to the notion of
distance adopted. As a further contribution we will also show that
from...
Currently displaying 61 –
80 of
86