On the complexity of task allocation

A detailed study is presented on the combinatorial optimization problem of allocating parallel tasks to a parallel computer. Depending on two application/machine-specific parameters, both a sequential and a parallel optimal allocation phase are shown to exist. A sudden “phase” transition is observed if one of these parameters is varied. Simulated annealing is used to find the optimal allocations, which is justified by the self-similar structure of the task allocation energy landscape. It is shown that the difficulty of finding optimal allocations behaves anomalously near the transition, analogous to critical slowing down of simulated equilibration at second-order phase transitions. © 1997 John Wiley & Sons, Inc.     

Easy and hard bottleneck location problems

We consider a bottleneck location problem on a graph and present an efficient (polynomial time) algorithm for solving it. The problem involve the location of K noxious facilities that are to be placed as far as possilbe from the other facilities, and the objective is to maximize the minimum distance from the noxious facilities to the others. We then show that two other bottleneck (min-max) location problems, finding K-centers and absolute K-centers of a graph appear to be very difficult to solve even for reasonably good approximate solutions.     

Forbidden subposet problems in the grid

For posets P and Q, extremal and saturation problems about weak and strong P-free subposets of Q have been studied mostly in the case Q is the Boolean poset $Q_n$, the poset of all subsets of an n-element set ordered by inclusion. In this paper, we study some instances of the problem with Q being the grid, and its connections to the Boolean case and to the forbidden submatrix problem.     

Norm statistics and the complexity of clustering problems

In this paper we introduce a new class of clustering problems. These are similar to certain classical problems but involve a novel combination of ?_p-statistics and ?_q norms. We discuss a real world application in which the case p=2 and q=1 arises in a natural way. We show that, even for one dimension, such problems are NP-hard, which is surprising because the same 1-dimensional problems for the ‘pure’ ?₂-statistic and ?₂ norm are known to satisfy a ‘string property’ and can be solved in polynomial time. We generalize the string property for the case p=q. The string property need not hold when q≤p−1 and we show that instances may be constructed, for which the best solution satisfying the string property does arbitrarily poorly. We state some open problems and conjectures.     

On the complexity of the bondage and reinforcement problems

Let G=(V,E)$G=(V,E)$ be a graph. A subset D⊆V$D\subseteq V$ is a dominating set if every vertex not in D$D$ is adjacent to a vertex in D$D$. A dominating set D$D$ is called a total dominating set if every vertex in D$D$ is adjacent to a vertex in D$D$. The domination (resp. total domination) number of G$G$ is the smallest cardinality of a dominating (resp. total dominating) set of G$G$. The bondage (resp. total bondage) number of a nonempty graph G$G$ is the smallest number of edges whose removal from G$G$ results in a graph with larger domination (resp. total domination) number of G$G$. The reinforcement (resp. total reinforcement) number of G$G$ is the smallest number of edges whose addition to G$G$ results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

Qubit complexity of continuous problems

The number of qubits used by a quantum algorithm will be a crucial computational resource for the foreseeable future. We show how to obtain the classical query complexity for continuous problems. We then establish a simple formula for a lower bound on the qubit complexity in terms of the classical query complexity.     

Parallel complexity of sorting problems

The paper discusses three basic sorting problems using a parallel model, the selection problem, the merging problem and the full sorting problem. The merging problem is completely solved, for the other two upper and lower bounds for the cost functions are derived.     

Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem

We study the computational complexity of the Spare Capacity Allocation problem arising in optical networks that use a shared mesh restoration scheme. In this problem we are given a network with edge capacities and point-to-point demands, and the goal is to allocate two edge-disjoint paths for each demand (a working path and a so-called restoration path, which is activated only if the working path fails) so that the capacity constraints are satisfied and the total cost of the used and reserved bandwidth is minimized. We focus on the setting where we deal with a group of demands together, and select their restoration paths simultaneously in order to minimize the total cost. We investigate how the computational complexity of this problem is affected by certain parameters, such as the number of restoration paths to be selected, or the treewidth of the network graph. To analyze the complexity of the problem, we introduce a generalization of the Steiner Forest problem that we call Multicost Steiner Subgraph. We study its parameterized complexity, and identify computationally easy and hard cases by providing hardness proofs as well as efficient (fixed-parameter tractable) algorithms.     

Average-case complexity and decision problems in group theory

We investigate the average-case complexity of decision problems for finitely generated groups, in particular, the word and membership problems. Using our recent results on “generic-case complexity”, we show that if a finitely generated group G has word problem solvable in subexponential time and has a subgroup of finite index which possesses a non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem of G is linear time, uniformly with respect to the collection of all length-invariant measures on G. This results applies to many of the groups usually studied in geometric group theory: for example, all braid groups B_n, all groups of hyperbolic knots, many Coxeter groups and all Artin groups of extra-large type.     

Cooperative games and cost allocation problems

The objective of this paper is to provide a general view of the literature of applications of transferable utility cooperative games to cost allocation problems. This literature is so large that we concentrate on some relevant contributions in three specific areas: transportation, natural resources and power industry. We stress those applications dealing with costs and with problems arisen outside the academic world.     

On the complexity of some data analysis problems

NP-completeness of certain discrete optimization problems is proved. These are the problems to which one can reduce some important problems arising in data analysis when certain subsets of vectors are sought.     

On the complexity of Slater’s problems

Given a tournament T, Slater’s problem consists in determining a linear order (i.e. a complete directed graph without directed cycles) at minimum distance from T, the distance between T and a linear order O being the number of directed edges with different orientations in T and in O. This paper studies the complexity of this problem and of several variants of it: computing a Slater order, computing a Slater winner, checking that a given vertex is a Slater winner and so on.