Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling

We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i’s cost parameter by a cost function of agent j. The cost function of agent j is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is NP-hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations.     

Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$k$ edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.     

View-obstruction problem for 3-dimensional spheres

The view-obstruction problem for ann-dimensional closed convex bodyC containing the origin in its interior has been formulated by T. W. Cusick in 1973. The problem is to determine the constantK(C) defined to be the infimum of those >0 such that for any rayL starting from the origin and lying in the positive quadrant there are non-negative integersm ₁,...,m _n for whichL intersects C+(m ₁+1/2,...,m _n +1/2). Here a conjecture of T. W. Cusick for the 3-dimensional spheres with centre 0 is proved. In fact an infinite sequence of isolated minima is obtained.Dedicated to Professor R. P. Bambah on the Occasion of his Sixtieth Birthday     

Complexity of 4-dimensional h-cobordisms

In this paper we define the complexity of 4-dimensional h-cobordisms by counting the number of flow-lines between the critical points and prove the existence of h-cobordisms with arbitrary large complexity. Oblatum 24-VI-1997 & 13-II-1998 / Published online: 10 February 1999     

The view-obstruction problem for 3-dimensional spheres

LetC be ann-dimensional sphere with diameter 1 and center at the origin inE ⁿ . The view-obstruction problem forn-dimensional spheres is to determine a constant ν(n) to be the lower bound of those α for which any half-lineL, given byx _i =a _i t (i=1,2,...,n) where parametert≥0 anda _i (i=1,2,...,n) are positive real numbers, intersects

A case of the 3-dimensional problem of Apollonius

Summary Inn-dimensions the problem of Apollonius is to determine the (n–1)-spheres tangent ton+1 given (n–1)-spheres. In case no two of the given (n–1)-spheres intersect and no three have the property that one separates the other two, the expected number of solutions is 2 ⁿ⁺¹. Whenn=2 this special problem does indeed always have 8 solutions, but for higher dimensions it turns out that the number of solutions becomes dependent on the relative size and location of the given (n–1)-spheres. We describe in detail the dependence of the number of solutions in the case of the 3-dimensional problem of Apollonius on the 6 inversively invariant parameters that describe configurations of 4 given spheres. We find that the number of solutions, if finite, can be any integer from 0 to 16 and, if infinite, can be a one-, two- or three-fold infinity where the stated multiplicity refers to the number of one-parameter families of solutions that are present.     

Pole assignment problem for a second-order system

We solve the pole assignment problem for a second-order two-input–two-output linear dynamical system with the use of a static feedback control.     

Reducing the elastic generalized assignment problem to the standard generalized assignment problem

The elastic generalized assignment problem (eGAP) is a natural extension of the generalized assignment problem (GAP) where the capacities are not fixed but can be adjusted; this adjustment can be expressed by continuous variables. These variables might be unbounded or restricted by a lower or upper bound, respectively. This paper concerns techniques aiming at reducing several variants of eGAP to GAP, which enables us to employ standard approaches for the GAP. This results in a heuristic, which can be customized in order to provide solutions having an objective value arbitrarily close to the optimal.     

The chairman assignment problem

Suppose k states form a union and every year a union chairman has to be selected in such a way that at any time the accumulated number of chairmen from each state is proportional to its weight. In this paper a simple algorithm for a chairman assignment is given which guarantees a small discrepancy. The situation that not only states form unions, but also unions form federations, etc., with one overall organization is also investigated.     

A personnel assignment problem

The following personnel assignment problem is considered. Let (T, ?) be a linearly ordered set where T is a set (of people), and let (P, ?) be a partially ordered set where P, a set of positions of two types, is of the same cardinality as T. Each person i in T is to be assigned to a position. A feasible assignment of personnel to positions is an embedding of (P, ?) in (T, ?). Given measures of each person's effectiveness in both types of positions, an optimal assignment maximizes the total measure of effectiveness. The general assignment problem is shown to be NP-complete. O(n log n) algorithms for two special cases of the problem are presented.     

Complexity of the Frobenius problem

Consider the Frobenius Problem: Given positive integersa ₁,...,a _n witha _i 2 and such that their greatest common divisor is one, find the largest natural number that is not expressible as a non-negative integer combination ofa ₁,...,a _n. In this paper we prove that the Frobenius problem is NP-hard, under Turing reductions.     

Network flow assignment as a fixed point problem

This paper deals with the user equilibrium problem (flow assignment with equal journey time by alternative routes) and system optimum (flow assignment with minimal average journey time) in a network consisting of parallel routes with a single origin-destination pair. The travel time is simulated by arbitrary smooth nondecreasing functions. We prove that the equilibrium and optimal assignment problems for such a network can be reduced to the fixed point problem expressed explicitly. A simple iterative method of finding equilibriumand optimal flow assignment is developed. The method is proved to converge geometrically; under some fairly natural conditions the method is proved to converge quadratically.     

Complexity of a scheduling problem with controllable processing times

We consider the problem of scheduling a set of independent jobs on a single machine so as to minimize the total weighted completion time, subject to the constraint that the total compression cost is less than or equal to a fixed amount. The complexity of this problem is mentioned as an open problem. In this note we show that the problem is NP-hard.     

Complexity of the min-max and min-max regret assignment problems

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment problem is strongly NP-hard.     

On the bottleneck assignment problem

In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is shown that any critical solution yields a global optimum. This theorem is then used as a basis to develop a general method to solve max-min permutation problems.This work was carried out by the junior author while holding a Purdue University Fellowship.     

The dynamic frequency assignment problem

In this paper, we consider a frequency assignment problem occurring in a military context. The main originality of the problem pertains to its dynamic dimension: new communications requiring frequency assignments need to be established throughout a battlefield deployment. The problem resolution framework decomposes into three phases: assignment of an initial kernel of communications, dynamic assignment of new communication links and a repair process when no assignment is possible. Different solution methods are proposed and extensive computational experiments are carried out on realistic instances.