Relaxation heuristics for a generalized assignment problem

We propose relaxation heuristics for the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. Using Lagrangian or surrogate relaxation, the heuristics perform a subgradient search obtaining feasible solutions. Relaxation considers a vector of multipliers for the capacity constraints. The resolution of the Lagrangian is then immediate. For the surrogate, the resulting problem is a multiple choice knapsack that is again relaxed for continuous values of the variables, and solved in polynomial time. Relaxation multipliers are used with an improved heuristic of Martello and Toth or a new constructive heuristic to find good feasible solutions. Six heuristics are tested with problems of the literature and random generated problems. Best results are less than 0.5% from the optimal, with reasonable computational times for an AT/386 computer. It seems promising even for problems with correlated coefficients.     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

New exact solitary-wave special solutions for the nonlinear dispersive K(m, n) equations

In this paper, we study the nonlinear dispersive K(m, n) equations: u_t + (u^m)_x − (uⁿ)_xxx = 0 which exhibit solutions with solitary patterns. New exact solitary solutions are found. The two special cases, K(2, 2) and K(3, 3), are chosen to illustrate the concrete features of the decomposition method in K(m, n) equations. The nonlinear equations K(m, n) are studied for two different cases, namely when m = n being odd and even integers. General formulas for the solutions of K(m, n) equations are established.     

On Certain C-Test Words for Free Groups

Let F_m be a free group of a finite rank m ≥ 2 and let X_i, Y_j be elements in F_m. A non-empty word w(x₁,…,x_n) is called a C-test word in n letters for F_m if, whenever (X₁,…,X_n) = w(Y₁,…,Y_n) ≠ 1, the two n-typles (X₁,…,X_n) and (Y₁,…,Y_n) are conjugate in F_m. In this paper we construct, for each n ≥ 2, a C-test word v_n(x₁,…,x_n) with the additional property that v_n(X₁,…,X_n) = 1 if and only if the subgroup of F_m generated by X₁,…,X_n is cyclic. Making use of such words v_m(x₁,…,x_m) and v_m + 1(x₁,…,x_m + 1), we provide a positive solution to the following problem raised by Shpilrain: There exist two elements u₁, u₂ ∈ F_m such that every endomorphism ψ of F_m with non-cyclic image is completely determined by ψ(u₁), ψ(u₂).     

Fast Rectangular Matrix Multiplication and Applications

First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of ann×nmatrix by ann×n²matrix in arithmetic timeO(n^ω),ω=3.333953…, which is less by 0.041 than the previous record 3.375477…. Then we present fast multiplication algorithms for matrix pairs of arbitrary dimensions, estimate the asymptotic running time as a function of the dimensions, and optimize the exponents of the complexity estimates. For a large class of input matrix pairs, we improve the known exponents. Finally we show three applications of our results:   (a) we decrease from 2.851 to 2.837 the known exponent of the work bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of ann×nmatrix, as well as for the solution to a nonsingular linear system ofnequations,   (b) we asymptotically accelerate the known sequential algorithms for the univariate polynomial composition mod xⁿ, yielding the complexity boundO(n^1.667) versus the old record ofO(n^1.688), and for the univariate polynomial factorization over a finite field, and   (c) we improve slightly the known complexity estimates for computing basic solutions to the linear programming problem withmconstraints andnvariables.     

New exact solution profiles of the nonlinear dispersion Drinfel’d–Sokolov (D(m, n)) system

In this paper, to understand the role of nonlinear dispersion in the coupled systems, the nonlinear dispersion Drinfel’d–Sokolov system (called D(m, n) system) is investigated. As a consequence, many types of compacton and solitary pattern solutions are obtained. Moreover, some solitary wave solutions are also deduced for differential parameters m, n. When n = 1, the D(m, 1) system with linear dispersion is shown to possess also compacton and solitary pattern solutions, which contain the known results. Moreover, some rational solutions of D(m, n) system are also deduced.     

Exact special solitary solutions with compact support for the nonlinear dispersive K(m, n) equations

The nonlinear dispersive K(m, n) equations, u_t−(u^m)_x−(uⁿ)_xxx = 0 which exhibit compactons: solitons with compact support, are studied. New exact solitary solutions with compact support are found. The two special cases, K(2, 2) and K(3, 3), are chosen to illustrate the concrete features of the decomposition method in K(m, n) equations. General formulas for the solutions of K(m, n) equations are established.     

A rank-based approach to the sequential selection and assignment problem

In the classical sequential assignment problem, “machines” are to be allocated sequentially to “jobs” so as to maximize the expected total return, where the return from an allocation of job j to machine k is the product of the value x_j of the job and the weight p_k of the machine. The set of m machines and their weights are given ahead of time, but n jobs arrive in sequential order and their values are usually treated as independent, identically distributed random variables from a known univariate probability distribution with known parameter values. In the paper, we consider a rank-based version of the sequential selection and assignment problem that minimizes the sum of weighted ranks of jobs and machines. The so-called “secretary problem” is shown to be a special case of our sequential assignment problem (i.e., m = 1). Due to its distribution-free property, our rank-based assignment strategy can be successfully applied to various managerial decision problems such as machine scheduling, job interview, kidney allocations for transplant, and emergency evacuation plan of patients in a mass-casualty situation.     

A dual transformation between SO(n + 1) and SO(n, 1) and its geometric applications

There is a dual transformation between SO(n + 1)?{(00-component) = 0} and SO(n, 1). This transformation makes clear the relations how orthogonal axes look like in two spaces, Euclidean space and Minkowski space.     

Uniform duality in semi-infinite convex optimization

We study infinite sets of convex functional constraints, with possibly a set constraint, under general background hypotheses which require closed functions and a closed set, but otherwise do not require a Slater point. For example, when the set constraint is not present, only the consistency of the conditions is needed. We provide hypotheses, which are necessary as well as sufficient, for the overall set of constraints to have the property that there is no gap in Lagrangean duality for every convex objective function defined on ℝⁿ. The sums considered for our Lagrangean dual are those involving only finitely many nonzero multipliers. In particular, we recover the usual sufficient condition when only finitely many functional constraints are present. We show that a certain compactness condition in function space plays the role of finiteness, when there are an infinite number of functional constraints. The author's research has been partially supported by Grant ECS8001763 of the National Science Foundation.     

Inverse dynamics of underactuated mechanical systems: A simple case study and experimental verification

Underactuated systems are featured by fewer control inputs than the degrees-of-freedom, m < n. The determination of an input control strategy that forces such a system to complete a set of m specified motion tasks is a challenging task, and the explicit solution existence is conditioned to differential flatness of the problem. The flatness-based solution denotes that all the 2n states and m control inputs can be algebraically expressed in terms of the m specified outputs and their time derivatives up to a certain order, which is in practice attainable only for simple systems. In this contribution the problem is posed in a more practical way as a set of index-three differential–algebraic equations, and the solution is obtained numerically. The formulation is then illustrated by a two-degree-of-freedom underactuated system composed of two rotating discs connected by a torsional spring, in which the pre-specified motion of one of the discs is actuated by the torque applied to the other disc, n = 2 and m = 1. Experimental verification of the inverse simulation control methodology is reported.     

Generation of n × m-scroll attractors in a two-port RCL network with hysteresis circuits

In this paper, the generation of n × m-scroll attractors based on a two-port network is presented. The two-port network is built according to the RCL circuit suggested in the conventional Chua’s circuit. By appending hysteresis voltage controlled devices on this two-port network, n-scroll and n × m-scroll attractors can be duly obtained both in simulations and experiments.     

A new approach to solving the multiple traveling salesperson problem using genetic algorithms

The multiple traveling salesperson problem (MTSP) involves scheduling m > 1 salespersons to visit a set of n > m locations so that each location is visited exactly once while minimizing the total (or maximum) distance traveled by the salespersons. The MTSP is similar to the notoriously difficult traveling salesperson problem (TSP) with the added complication that each location may be visited by any one of the salespersons. Previous studies investigated solving the MTSP with genetic algorithms (GAs) using standard TSP chromosomes and operators. This paper proposes a new GA chromosome and related operators for the MTSP and compares the theoretical properties and computational performance of the proposed technique to previous work. Computational testing shows the new approach results in a smaller search space and, in many cases, produces better solutions than previous techniques.     

The average path length of scale free networks

In this paper, the exact solution of average path length in Barabási–Albert model is given. The average path length is an important property of networks and attracts much attention in many areas. The Barabási–Albert model, also called scale free model, is a popular model used in modeling real systems. Hence it is valuable for us to examine the average path length of scale free model. There are two answers, regarding the exact solution for the average path length of scale free networks, already provided by Newman and Bollobas respectively. As Newman proposed, the average path length grows as log(n) with the network size n. However, Bollobas suggested that while it was true when m = 1, the answer changed to log(n)/log(log(n)) when m > 1. In this paper, as we propose, the exact solution of average path length of BA model should approach log(n)/log(log(n)) regardless the value of m. Finally, the simulation is presented to show the validity of our result.     

An exact algorithm for the knapsack sharing problem with common items

We are concerned with a variation of the knapsack problem as well as of the knapsack sharing problem, where we are given a set of n items and a knapsack of a fixed capacity. As usual, each item is associated with its profit and weight, and the problem is to determine the subset of items to be packed into the knapsack. However, in the problem there are s players and the items are divided into s + 1 disjoint groups, N_k (k = 0, 1, … , s). The player k is concerned only with the items in N₀ ∪ N_k, where N₀ is the set of ‘common’ items, while N_k represents the set of his own items. The problem is to maximize the minimum of the profits of all the players. An algorithm is developed to solve this problem to optimality, and through a series of computational experiments, we evaluate the performance of the developed algorithm.     

Anomalous diffusion approach to dielectric spectroscopy data with independent low- and high-frequency exponents

We advance a perspective outcome of tempered α-stable processes used in modeling of anomalous diffusion, a physical mechanism underlying the non-Debye relaxations. The tempered processes are characterized by a heavy tail truncation in time and have finite moments, but they also save some useful features of a purely skewed α-stable process. Due to these features, the relaxation phenomena get a transient character being shown in their asymptotic behavior. From the stochastic subordination scenario of the tempered anomalous diffusion we derive relaxation functions with independent low- and high-frequency exponents falling in the range (0, 1]. Those functions can be used to model all types of experimentally observed two-power-law relaxation patterns.     

Surrogate duality in a branch-and-bound procedure for integer programming

The existence of efficient techniques such as subgradient search for solving Lagrangean duals has led to some very successful applications of Lagrangean duality in solving specially structured discrete problems. While surrogate duals have been theoretically shown to provide stronger bounds, the complexity of surrogate dual multiplier search has discouraged their employment in solving integer programs. We have recently suggested a new strategy for computing surrogate dual values that allows us to directly use established Lagrangean search methods for exploring surrogate dual multipliers. This paper considers the problem of incorporating surrogate duality within a branch-and-bound procedure for solving integer programming problems. Computational experience with randomly generated multiconstraint knapsack problems is also reported.     

Parallel Construction and Query of Index Data Structures for Pattern Matching on Square Matrices

We describe fast parallel algorithms for building index data structures that can be used to gather various statistics on square matrices. The main data structure is the Lsuffix tree, which is a generalization of the classical suffix tree for strings. Given ann×ntext matrixA, we build our data structures inO(log n) time withn²processors on a CRCW PRAM, so that we can quickly processAin parallel as follows: (i) report some statistical information aboutA, e.g., find the largest repeated square submatrices that appear at least twice inAor determine, for each position inA, the smallest submatrix that occurs only there; (ii) given, on-line, anm×mpattern matrixPAT, check whether it occurs inA. We refer to the above two kinds of operations as queries and point out that they have applications to visual databases and two-dimensional data compression. Query (i) takesO(log n) time withn²/log nprocessors and query (ii) takesO(log m) time withm²/log mprocessors. The query algorithms are work optimal while the construction algorithm is work optimal only for arbitrary and large alphabets.