On the average case complexity of some P-complete problems
Parallel approximation to high multiplicity scheduling problems smooth multi-valued quadratic programming
We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...
On the Average Case Complexity of Some P-complete Problems
We show that some classical P-complete problems can be solved efficiently in NC. The probabilistic model we consider is the sample space of input descriptions of the problem with the underlying distribution being the uniform one. We present parallel algorithms that use a polynomial number of processors and have expected time upper bounded by ( ln 4 + (1))log , asymptotically with high probability, where is the instance size.
Parallel approximation to high multiplicity scheduling problems smooth multi-valued quadratic programming
We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the and the . These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are -complete and hence cannot be efficiently solved in parallel unless = . To deal with the parallel approximablity of these problems, we show first a parallel approximation procedure to a subclass of multi-valued...
On the proper intervalization of colored caterpillar trees
This paper studies the computational complexity of the problem (), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the and a graph layout problem the (). We show a dichotomy: the and the are NP-complete for colored caterpillars of hair length 2, while both problems are in P for colored caterpillars of hair length 2. For the hardness results we provide a reduction from the , while the polynomial...
On the hardness of game equivalence under local isomorphism
We introduce a type of isomorphism among strategic games that we call . Local isomorphisms is a weaker version of the notions of strong and weak game isomorphism introduced in [J. Gabarro, A. Garcia and M. Serna, 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 local isomorphism is equivalent to the...
Asymptotical behaviour of some non-uniform measures
On the complexity of problems on simple games
Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation...
On the complexity of problems on simple games
Simple games cover voting systems in which a single alternative, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games....
Page 1