Individual items of flow in a telecommunications or a transportation network may need to beseparated by a minimum distance or time, called a “headway”. If link dependent, such restrictions in general have the effect that the minimum time path for a “convoy” of items to travel from a given origin to a given destinationwill depend on the size of the convoy. The Quickest Path problemseeks a path to minimise this convoy travel time.A closely related bicriterion problem is the Maximum Capacity Shortest Path problem. For this latter problem,an effective implementation is devised for an algorithm to determine desired sets of efficient solutions which in turn facilitates the searchfor a “best” compromise solution. Numerical experience with the algorithm is reported.

We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than 5/4 (unless P = NP). This result is an extension of the result of Hoogeveen et al. [CITE] who proved that there is no polynomial time ρ-approximation algorithm with p < 7/6 for the classical UET-UCT scheduling problem with homogeneous communication delays and an unrestricted number of identical machines.

In this work scheduling multiprocessor tasks on two parallel identical processors is considered.Multiprocessor tasks can be executed by more than one processorat the same moment of time.We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness.Cases with ready times, due-dates and precedence constraintsare discussed.

We consider a special packing-covering pair of problems. Thepacking problem is a natural generalization of finding a(weighted) maximum independent set in an interval graph, thecovering problem generalizes the problem of finding a (weighted)minimum clique cover in an interval graph. The problem pairinvolves weights and capacities; we consider the case of unitweights and the case of unit capacities. In each case we describea simple algorithm that outputs a solution to the packing problemand to the covering problem that are within a factor of 2 of eachother. Each of these results implies an approximative min-maxresult. For the general case of arbitrary weights and capacitieswe describe an LP-based (2 + ε)-approximation algorithm forthe covering problem. Finally, we show that, unlessP = NP, the covering problem cannot be approximated inpolynomial time within arbitrarily good precision.

We analyze the convergence of the prox-regularization algorithmsintroduced in [1], to solve generalized fractional programs,without assuming that the optimal solutions set of the consideredproblem is nonempty, and since the objective functions arevariable with respect to the iterations in the auxiliary problemsgenerated by Dinkelbach-type algorithms DT1 and DT2, we considerthat the regularizing parameter is also variable. On the otherhand we study the convergence when the iterates are onlyηk -minimizers of the auxiliary problems. This situation ismore general than the one considered in [1]. We also give someresults concerning the rate of convergence of these algorithms,and show that it is linear and some times superlinear for someclasses of functions. Illustrations by numerical examples aregiven in [1].

We investigate the minima of functionals of the form $$\int_{[a,b]}g(\dot u(s)){\rm d}s$$ where g is strictly convex. The admissible functions $u:[a,b]\longrightarrow\mathbb{R}$ are not necessarily convex and satisfy $u\leq f$ on [a,b], u(a)=f(a), u(b)=f(b), f is a fixed function on [a,b].We show that the minimum is attained by $\bar f$ , the convex envelope of f.

The signed similarities aggregation problem is solved with a booleanmethod derived from the Faure and Malgrange algorithm.The method is adequate either for integer similarities orreal similarites, and multiple solutions can be enumerated.It needs a space amount equal to three times the input data size.