Scheduling unit-length jobs with precedence constraints of small height

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.     

The pairwise flowtime network construction problem

It is required to find an optimal order of constructing the edges of a network so as to minimize the sum of the weighted connection times of relevant pairs of vertices. Construction can be performed anytime anywhere in the network, with a fixed overall construction speed. The problem is strongly NP-hard even on stars. We present polynomial algorithms for the problem on trees with a fixed number of leaves, and on general networks with a fixed number of relevant pairs.     

Partitioning Perfect Graphs into Stars

The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same‐size stars, a problem known to be NP‐complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial‐time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP‐complete cases, for example, on grid graphs and chordal graphs.     

Quaternion non-linear filter for estimation of rotating body attitude

A problem of optimal estimation of a rotating vehicle's attitude with both differential equations of motion and observations of stars by onboard equipment is considered. The problem is formulated like a determinate non-linear Kalman filter problem in quaternion terms. An exact analytical solution of the problem is also found in quaternion terms. Various types of solutions in accordance with a mutual arrangement of observed stars are presented. An example of only one observed star is demonstrated to support the method. The method is also suited for geodetic applications, e.g. geodetic positioning and navigation systems.     

Menus of kuratowski subgraphs

Motivated by heuristic embedding algorithms, this paper is concerned with the organization of potentially large lists of Kuratowski subgraphs of an arbitrary nonpianar graph. A graphical structure called a "nearly Hamiltonian" graph is defined. It is shown that lists of Kuralowski subgraphs can be lexicographically organized in such structures. It is shown that any nonpianar graph contains such structures and at least one such structure with a nonempty list of Kuratowski subgraphs can be located in linear time in ihe edges of the graph.     

圆型限制性三体问题中双恒星系统的存在性

在圆型限制性三体问题的研究中，研究较多的是在其中一体附近的运动。本文研究远离两个大质量恒星的行星的运行情况，在此范围内，使用KAM理论研究大振幅轨道的存在性，说明了星系中双恒星系统的存在性，而这一现象已被天文学家所观察到。     

Fair resource allocation for different scenarios of demands

This paper considers a resource allocation problem, which objective is to treat fairly all the system users. Usually the requests cannot be entirely predicted, but the manager can forecast the request evolution, this leading to a set of possible scenarios. Such a problem arises for instance in network bandwidth allocation as well as in storage space management. It also appears in the management of computer systems, such as computational grids or in cloud computing, when teams share a common pool of machines. Problems of fair resource sharing arise among users with equal access right but with different needs.Here the problem is tackled by a multi-criteria model, where one criterion is associated to one scenario. A solution is a policy, which provides an allocation for each scenario. An algorithm is proposed and analysed that lists all solutions which are Pareto optimal with regard to the different possible user request scenarios. The algorithm is used offline, but can be adapted, with some additional hypothesis, to be used online.     

Optimal shift coloring of trees

This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial-time algorithm. We also provide direct optimal solutions for special trees like stars and paths.     

Branch duplication for the construction of multiple eigenvalues in an Hermitian matrix whose graph is a tree

Suppose that the eigenvalues of an Hermitian matrix A whose graph is a tree T are known, as well as the eigenvalues of the principal submatrix of A corresponding to a certain branch of T. A method for constructing a larger tree T?', in which the branch is ‘`duplicated’', and an Hermitian matrix A′ whose graph is T?' is described. The eigenvalues of A' are all of those of A, together with those corresponding to the branch, including multiplicities. This idea is applied (1) to give a solution to the inverse eigenvalue problem for stars, (2) to prove that the known diameter lower bound, for the minimum number of distinct eigenvalues among Hermitian matrices with a given graph, is best possible for trees of bounded diameter, and (3) to increase the list of trees for which all possible lists for the possible spectra are know. A generalization of the basic branch duplication method is presented.     

Detecting irregular orbits in gravitational N-body simulations

We present a qualitative diagnostic based on the continuous wavelet transform, for the detection of irregular behaviour in time series of particle simulations. We apply the method to three qualitatively different gravitational 3-body encounters. The intrinsic irregular behaviour of these encounters is well reproduced by the presented method, and we show that the method accurately identifies the irregular regime in these encounters. We also provide an instantaneous quantification for the degree of irregularity in these simulations. Furthermore we demonstrate how the method can be used to analyse larger systems by applying it to simulations with 100-particles. It turns out that the number of stars on irregular orbits is systematically larger for clusters in which all stars have the same mass compared to a multi-mass system. The proposed method provides a quick and sufficiently accurate diagnostic for identifying stars on irregular orbits in large scale N-body simulations.     

Tuning Garwick's algorithm for repacking sequential storage

Garwick's algorithm, for repacking LIFO lists stored in a contiguous block of memory, bases the allocation of remaining space upon both sharing and previous stack growth. A system whereby the weight applied to each method can be adjusted according to the current behavior of the stacks is discussed.We also investigate the problem of determining during memory repacking that the memory is used to saturation and the driving program should therefore be aborted. The tuning parameters studied here seem to offer no new grasp on this problem.     

Integer programming models for the multidimensional assignment problem with star costs

We consider a variant of the multidimensional assignment problem (MAP) with decomposable costs in which the resulting optimal assignment is described as a set of disjoint stars. This problem arises in the context of multi-sensor multi-target tracking problems, where a set of measurements, obtained from a collection of sensors, must be associated to a set of different targets. To solve this problem we study two different formulations. First, we introduce a continuous nonlinear program and its linearization, along with additional valid inequalities that improve the lower bounds. Second, we state the standard MAP formulation as a set partitioning problem, and solve it via branch and price. These approaches were put to test by solving instances ranging from tripartite to 20-partite graphs of 4 to 30 nodes per partition. Computational results show that our approaches are a viable option to solve this problem. A comparative study is presented.     

Analysis of pseudo-periodic chronological series with irregularly time-spaced data in view to their prediction. III. Symbolic analysis

The problem originates from the necessity to predict luminosities of large-amplitude variable stars that are to be observed by the astronomical satellite HIPPARCOS. The data have a specific character: they are unequally time-spaced and can be missing during a long time in comparison to the pseudo-period. So the classical method of time-series analysis must be adapted and new methods are to be searched. In this paper we present a symbolic solution.     

Path problems in generalized stars, complete graphs, and brick wall graphs

Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors.     

Assignment Using Choice Lists

This paper examines the problem of assigning items to people, given that each person lists the items in the order in which he would prefer them. Three types of assignment function are examined, namely stable, bottleneck and numerical, and the advantages and disadvantages of each are discussed. The effect of allowing equal choices in the lists (weak preference ordering) is also examined.     

The stable marriage problem with master preference lists

We study variants of the classical stable marriage problem in which the preferences of the men or the women, or both, are derived from a master preference list. This models real-world matching problems in which participants are ranked according to some objective criteria. The master list(s) may be strictly ordered, or may include ties, and the lists of individuals may involve ties and may include all, or just some, of the members of the opposite sex. In fact, ties are almost inevitable in the master list if the ranking is done on the basis of a scoring scheme with a relatively small range of distinct values. We show that many of the interesting variants of stable marriage that are NP-hard remain so under very severe restrictions involving the presence of master lists, but a number of special cases can be solved in polynomial time. Under this master list model, versions of the stable marriage problem that are already solvable in polynomial time typically yield to faster and/or simpler algorithms, giving rise to simple new structural characterisations of the solutions in these cases.     

Approximation hardness of min-max tree covers

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours.     

A priority list based heuristic for the job shop problem

A priority list for the job shop scheduling problem is defined to be any permutation of a set of symbols where the symbol for each job appears as many times as the number of its operations. Every priority list can be associated in a natural way with a feasible schedule, and every feasible schedule arises in this way. Priority lists are therefore a representation of feasible schedules that avoid the problems normally associated with schedule infeasibility. As a result, the three ingredients of local search heuristics, namely picking initial starting schedules, constructing search neighbourhoods and computing makespans, become faster and easier when performed in the space of priority lists rather than in the space of feasible schedules. As an illustration of their usefulness, a priority list based simulated annealing heuristic is presented, which, although simple, is competitive with the current leading schedule based simulated annealing and tabu search heuristics.     

Stellar Hydrodynamic Equations for a Thin Disk Galaxy

Assuming that the motions of stars depart only slightly from circular, finite closed systems of stellar hydrodynamic equations are obtained for a disk galaxy by taking moments of the collisionless Boltzmann equation. The usual closure problem is avoided in that explicit expressions are obtained for the highest moments arising.