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.     

Percentile residual life orders

In this paper we study a family of stochastic orders of random variables defined via the comparison of their percentile residual life functions. Some interpretations of these stochastic orders are given, and various properties of them are derived. The relationships to other stochastic orders are also studied. Finally, some applications in reliability theory and finance are described. Copyright © 2010 John Wiley & Sons, Ltd.     

Solving a class of multiplicative programming problems via c-programming

In this note we show that many classes of global optimization problems can be treated most satisfactorily by classical optimization theory and conventional algorithms. We focus on the class of problems involving the minimization of the product of several convex functions on a convex set which was studied recently by Kunoet al. [3]. It is shown that these problems are typical composite concave programming problems and thus can be handled elegantly by c-programming [4]–[8] and its techniques.     

Derivation of the Tully—Fisher Law: Doubts About the Necessity and Existence of Halo Dark Matter

For disk galaxies the fourth power of the circular velocity ⁴ _c of stars around thecore of the galaxy is proportional to the luminosity L, ⁴ _c L (Tully—Fisher law).Since L is proportional to the mass M of the galaxy, it follows that ⁴ _c M.Newtonian mechanics, however, yields ² _c = GM/r for a circular motion. In orderto rectify this big difference, astronomers assume the existence of dark matter.We derive the equation of motion of a star moving in the central field of a galaxyand show that, for a circular motion, it yields a term of the form ⁴ _c GMc/,where G is Newton's gravitational constant, c is the speed of light, and is theHubble time. This puts in doubt the existence of halo dark matter for galaxies.     

A Lot-sizing Model for Just-in-time Manufacturing

We consider the problem of determining lot sizes of multiple items that are manufactured by a single capacitated facility. The manufacturing facility may represent a bottleneck processing activity on the shop floor or a storeroom that provides components to the shop floor. Items flow from the facility to a downstream facility, where they are assembled according to a specified mix. Just-in-time (JIT) manufacturing requires a balanced flow of items, in the proper mix, between successive facilities. Our model determines lot sizes of the various items based on available capacity and four attributes of each item: demand rate, holding cost, set-up time and processing time. Holding costs for each item accrue until the appropriate mix of items is available for shipment downstream. We develop a lot-sizing heuristic that minimizes total holding cost per time unit over all items, subject to capacity availability and the required mix of items.     

On parallel asynchronous high-order solutions of parabolic PDEs

In achieving significant speed-up on parallel machines, a major obstacle is the overhead associated with synchronizing the concurrent processes. This paper presents high-orderparallel asynchronous schemes, which are schemes that are specifically designed to minimize the associated synchronization overhead of a parallel machine in solving parabolic PDEs. They are asynchronous in the sense that each processor is allowed to advance at its own speed. Thus, these schemes are suitable for single (or multi) user shared memory or (message passing) MIMD multiprocessors. Our approach is demonstrated for the solution of the multidimensional heat equation, of which we present a spatial second-order Parametric Asynchronous Finite-Difference (PAFD) scheme. The well-known synchronous schemes are obtained as its special cases. This is a generalization and expansion of the results in [5] and [7]. The consistency, stability and convergence of this scheme are investigated in detail. Numerical tests show that although PAFD provides the desired order of accuracy, its efficiency is inadequate when performed on each grid point.In an alternative approach that uses domain decomposition, the problem domain is divided among the processors. Each processor computes its subdomain mostly independently, while the PAFD scheme provides the solutions at the subdomains' boundaries. We use high-order finite-difference implicit scheme within each subdomain and determine the values at subdomains' boundaries by the PAFD scheme. Moreover, in order to allow larger time-step, we use remote neighbors' values rather than those of the immediate neighbors. Numerical tests show that this approach provides high efficiency and in the case which uses remote neighbors' values an almost linear speedup is achieved. Schemes similar to the PAFD can be developed for other types of equations [3].This research was supported by the fund for promotion of research at the Technion.     

Ultraslow phonon-assisted collapse of tubular image states

We predict ultraslow collapse of “tubular image states” (TIS) on material surfaces. TIS are bound Rydberg-like electronic states formed at large distances (∼30 nm) from the surfaces of suspended circularly-symmetric nanowires, such as metallic C nanotubes. The states are formed in potential wells, resulting from a combination of the TIS-electron attraction to image charges in the nanotube and its centrifugal repulsion, caused by spinning around the tube. We demonstrate that TIS can collapse on the tube surface by passing their angular momentum l to circularly polarized flexural phonons excited in the tube. Our analysis shows that for highly detached TIS with l ? 6 the relaxation lifetimes are of the order of 10 ns-1 μs, while for l < 6 these lifetimes are reduced by several orders of magnitude.     

Octave-spanning supercontinuum generation of vortices in an As2S3 ring photonic crystal fiber

We propose As(2)S(3) ring photonic crystal fiber (PCF) for supercontinuum generation of optical vortex modes. Due to the large material index contrast between As(2)S(3) and air holes in the designed ring PCF, there is a two-orders-of-magnitude improvement of the difference between the effective refractive indices of different vortex modes compared with regular ring fiber. The design freedom of PCFs enables a low dispersion (<60 ps/nm/km variation in total) over a 522 nm optical bandwidth. Moreover, the vortex mode has a large nonlinear coefficient of 11.7/W/m at 1550 nm with a small confinement loss of <0.03 dB/m up to 2000 nm. An octave-spanning supercontinuum spectrum of the vortex mode is generated from 1196 to 2418 nm at -20 dB by launching a 120 fs pulse with a 60 W peak power at 1710 nm into a 1 cm long As(2)S(3) ring PCF.     

Efficient generation and multiplexing of optical orbital angular momentum modes in a ring fiber by using multiple coherent inputs

We propose an approach to efficiently generate and multiplex optical orbital angular momentum (OAM) modes in a fiber with a ring refractive index profile by using multiple coherent inputs from a Gaussian mode. By controlling the phase relationship of the multiple inputs, one can selectively generate OAM modes of different states l. By controlling both the amplitude and phase of the multiple inputs, multiple OAM modes can be generated simultaneously without additional loss coming from multiplexing. We show, by simulation, the generation of OAM modes (OAM state |l|<3) with mode purity greater than 99%. The power loss of generating and multiplexing seven modes is about 35%. A transmitter for an OAM-based mode-division multiplexing system is proposed based on the discrete Fourier transform between the data carried by the multiple inputs and the data carried by the OAM modes. The experimental implementation of the proposed approach could be achieved by integrating ring fiber, multicore fiber, and photonic integrated circuit technology.     

The O(N) vector model in the large-N limit revisited: multicritical points and double scaling limit

The multicritical points of the O(N)-invariant N vector model in the large-N limit are re-examined. Of particular interest are the subtleties involved in the stability of the phase structure at critical dimensions. In the limit N → ∞ while the coupling g → g_c in a correlated manner (the double scaling limit) a massless bound state O(N) singlet is formed and powers of 1/N are compensated by IR singularities. The persistence of the N → ∞ results beyond the leading order is then studied with particular interest in the possible existence of a phase with propagating small mass vector fields and a massless singlet bound state. We point out that under certain conditions the double scaled theory of the singlet field is non-interacting in critical dimensions.