Multi-armed bandit with sub-exponential rewards

We consider a general class of multi-armed bandits (MAB) problems with sub-exponential rewards. This is primarily motivated by service systems with exponential inter-arrival and service distributions. It is well-known that the celebrated Upper Confidence Bound (UCB) algorithm can achieve tight regret bound for MAB under sub-Gaussian rewards. There has been subsequent work by Bubeck et al. (2013) [4] extending this tightness result to any reward distributions with finite variance by leveraging robust mean estimators. In this paper, we present three alternative UCB based algorithms, termed UCB-Rad, UCB-Warm, and UCB-Hybrid, specifically for MAB with sub-exponential rewards. While not being the first to achieve tight regret bounds, these algorithms are conceptually simpler and provide a more explicit analysis for this problem. Moreover, we present a rental bike revenue management application and conduct numerical experiments. We find that UCB-Warm and UCB-Hybrid outperform UCB-Rad in our computational experiments.     

Emergy-based analysis of Beijing–Tianjin–Tangshan region in China

An emergy-based analysis was conducted for the Beijing–Tianjin–Tangshan urban agglomeration district from perspectives of emergy density, resource structure, environmental pressure and resource use efficiency during the period of 1991–2005. The results showed that Beijing, Tianjin and Tangshan as contiguous regions shared similar characters and evolving trends in certain aspects as emergy intensity and proportion of local renewable resources on the whole. As for the local resources availability, process efficiency and environmental pressure, however, these three cities have significant differences. With comparison of the other cities in China, it is shown that Beijing–Tianjin–Tangshan region has higher environment loading and lower sustainability level though enjoying rapid urbanization process and economic development. This study also suggests that the first priority on economic development competition within urban agglomeration regions may lead to the wasting of resources and redundant construction, while cooperative and rational selection for development pattern are the proper choice for coordinate regional development and long term sustainability to overcome resource restrictions.     

Blow-up of viscous heat-conducting compressible flows

We show the blow-up of strong solution of viscous heat-conducting flow when the initial density is compactly supported. This is an extension of Z. Xin's result [Z. Xin, Blow up of smooth solutions to the compressible Navier–Stokes equations with compact density, Comm. Pure Appl. Math. 51 (1998) 229–240] to the case of positive heat conduction coefficient but we do not need any information for the time decay of total pressure nor the lower bound of the entropy. We control the lower bound of second moment by total energy and obtain the exact relationship between the size of support of initial density and the existence time. We also provide a sufficient condition for the blow-up in case that the initial density is positive but has a decay at infinity.     

Partition Theorems for Left and Right Variable Words

In 1984 T. Carlson and S. Simpson established an infinitary extension of the Hales–Jewett Theorem in which the leftmost letters of all but one of the words were required to be variables. (We call such words left variable words.) In this paper we extend the Carlson–Simpson result for left variable words, prove a corresponding result about right variable words, and determine precisely the extent to which left and right variable words can be combined in such extensions. The results mentioned so far all involve a finite alphabet. We show that the results for left variable words do not extend to words over an infinite alphabet, but that the results for right variable words do extend.¹ This author acknowledges support received from the National Science Foundation via grant DMS-0070593.² This author acknowledges support received from the National Science Foundation via a post doctoral fellowship administered by the University of Maryland.     

Minimal concave cost rebalance of a portfolio to the efficient frontier

One usually constructs a portfolio on the efficient frontier, but it may not be efficient after, say three months since the efficient frontier will shift as the elapse of time. We then have to rebalance the portfolio if the deviation is no longer acceptable. The method to be proposed in this paper is to find a portfolio on the new efficient frontier such that the total transaction cost required for this rebalancing is minimal. This problem results in a nonconvex minimization problem, if we use mean-variance model. In this paper we will formulate this problem by using absolute deviation as the measure of risk and solve the resulting linearly constrained concave minimization problem by a branch and bound algorithm successfully applied to portfolio optimization problem under concave transaction costs. It will be demonstrated that this method is efficient and that it leads to a significant reduction of transaction costs. Key words.portfolio optimization – rebalance – mean-absolute deviation model – concave cost minimization – optimization over the efficient set – global optimizationMathematics Subject Classification (1991):20E28, 20G40, 20C20     

The vertex separator problem: algorithms and computations

This is a companion paper to our polyhedral study [1] of the Vertex Separator (VS) Problem. Given an undirected graph G, the VS problem consists in identifying a minimum-weight vertex set whose removal disconnects G, subject to bounds on the size of the resulting components. In this paper, we describe versions of a branch-and-cut algorithm based on the results of that polyhedral study. It uses two families of cuts, symmetric and asymmetric, for which we develop polynomial-time greedy separation routines. A heuristic to generate feasible separators is also used. A computational experiment on several data sets from the literature compares the performance of three versions of our algorithm to that of the commercial MIP solver XPRESS. This experiment throws a sharp light on the role of cut density, known to software developers but never before documented in the literature. It convincingly shows that the practical usefulness of cuts in integer programming depends not only on their strength, but also on their sparsity: everything else being equal, the smaller the cut support, the better. The power of the inequalities proposed here is well illustrated by the computational tests on dense graphs. This is in accordance with the previous observation, since the support of these cuts tends to decrease with graph density.Research supported by the Brazilian agencies FAPESP (grant 01/14205–6), CAPES (grant BEX 04444/02–2) and CNPq (grants 302588/02–7 and Pronex 664107/97–4).Research supported by the National Science Foundation through grant #DMI-0098427 and by the Office of Naval Research through contract N00014-97-1-0196.     

A Recommender System based on Idiotypic Artificial Immune Networks

The immune system is a complex biological system with a highly distributed, adaptive and self-organising nature. This paper presents an Artificial Immune System (AIS) that exploits some of these characteristics and is applied to the task of film recommendation by Collaborative Filtering (CF). Natural evolution and in particular the immune system have not been designed for classical optimisation. However, for this problem, we are not interested in finding a single optimum. Rather we intend to identify a sub-set of good matches on which recommendations can be based. It is our hypothesis that an AIS built on two central aspects of the biological immune system will be an ideal candidate to achieve this: Antigen–antibody interaction for matching and idiotypic antibody–antibody interaction for diversity. Computational results are presented in support of this conjecture and compared to those found by other CF techniques.Mathematics Subject Classifications (2000) 68Rxx, 68Txx, 90Bxx.     

Probability Density Function Estimation Using Gamma Kernels

We consider estimating density functions which have support on [0, ) using some gamma probability densities as kernels to replace the fixed and symmetric kernel used in the standard kernel density estimator. The gamma kernels are non-negative and have naturally varying shape. The gamma kernel estimators are free of boundary bias, non-negative and achieve the optimal rate of convergence for the mean integrated squared error. The variance of the gamma kernel estimators at a distance x away from the origin is O(n ^–4/5 x ^–1/2) indicating a smaller variance as x increases. Finite sample comparisons with other boundary bias free kernel estimators are made via simulation to evaluate the performance of the gamma kernel estimators.     

Collaboration among small shippers in a transportation market

Intense competition in markets is pushing companies to increase their operational efficiency. One possible way to achieve increased efficiency is through cooperation with other companies. We study the coalition formation among small shippers in a transportation market characterized by uncertain demand. We analyze the decisions taken by the coalition and study the effect of shipper characteristics on the benefit of collaboration. Analysis shows that the shippers always benefit from the coalition, but when the benefits are to be allocated, the coalition may not always guarantee the budget balance, which is elementary for sustainability of any coalition. Using a game theoretical approach this study proposes saving allocation mechanisms and discusses the conditions that lead to a balanced budget.     

On the shape–from–moments problem and recovering edges from noisy Radon data

We consider the problem of reconstructing a planar convex set from noisy observations of its moments. An estimation method based on pointwise recovering of the support function of the set is developed. We study intrinsic accuracy limitations in the shape–from–moments estimation problem by establishing a lower bound on the rate of convergence of the mean squared error. It is shown that the proposed estimator is near–optimal in the sense of the order. An application to tomographic reconstruction is discussed, and it is indicated how the proposed estimation method can be used for recovering edges from noisy Radon data.Mathematics Subject Classification (2000):62C20, 62G20, 94A12     

The application of the genetic algorithm to the minimization of potential energy functions

We adapted the genetic algorithm to minimize the AMBER potential energy function. We describe specific recombination and mutation operators for this task. Next we use our algorithm to locate low energy conformation of three polypeptides (AGAGAGAGA, A9, and [Met]-enkephalin) which are probably the global minimum conformations. Our potential energy minima are –94.71, –98.50, and –48.94 kcal/mol respectively. Next, we applied our algorithm to the 46 amino acid protein crambin and located a non-native conformation which had an AMBER potential energy 150 kcal/mol lower than the native conformation. This is not necessarily the global minimum conformation, but it does illustrate problems with the AMBER potential energy function. We believe this occurred because the AMBER potential energy function does not account for hydration.     

A note on the nucleolus and the kernel of the assignment game

There exist coalitional games with transferable utility which have the same core but different nucleoli. We show that this cannot happen in the case of assignment games. Whenever two assignment games have the same core, their nucleoli also coincide. To show this, we prove that the nucleolus of an assignment game coincides with that of its buyer–seller exact representative.I am grateful to C. Rafels and to the referees for their comments. Institutional support from research grants BEC 2002-00642 and SGR2001–0029 is also acknowledged.     

Embedded Spectrum on a Metric Graph (an Observation)

We suggest an elementary example of a simplest starlike graph that shows that the analytical disjunction may occur not on only at isolated points of the spectral parameter, but also on whole intervals. Bibliography: 1 title.__________Published in Zapiski Nauchnykh Seminarov POMI, Vol. 300, 2003, pp. 215–220     

An evaluation of technical efficiency and managerial correlates of solid waste management by Welsh SMEs using parametric and non-parametric techniques

Strong economic growth and environmental regulation stimulus make Welsh small and medium enterprises' (SMEs) sustainability performance merit investigation in the context of European Union (EU) sustainability initiatives. This is due in part to strong economic growth and the stimulus provided by environmental regulation. We use stochastic frontier analysis, a parametric econometric technique to generate estimates of the technical efficiency of solid waste management by 299 Welsh SMEs in 2003. We demonstrate that the ranking and efficiency scores of the Welsh SMEs studied correlate significantly with non-parametric data envelopment analysis efficiency measures and are related to the use of environmental auditing practices and the use of local business support groups, but not to monitoring of waste expenditures and publication of environmental policies.     

The Hartogs phenomenon in hypersurfaces with constant signature

In this paper we study the -equation with zero Cauchy data along a hypersurface with constant signature. Applications to the solvability of the tangential Cauchy–Riemann equations for smooth forms with compact support and currents on the hypersurface are given. We also prove that the Hartogs phenomenon holds in weakly 2-convex–concave hypersurfaces with constant signature of Stein manifolds.     

Denumerable controlled Markov chains with average reward criterion: Sample path optimality

We consider discrete-time nonlinear controlled stochastic systems, modeled by controlled Makov chains with denumerable state space and compact action space. The corresponding stochastic control problem of maximizing average rewards in the long-run is studied. Departing from the most common position which usesexpected values of rewards, we focus on a sample path analysis of the stream of states/rewards. Under a Lyapunov function condition, we show that stationary policies obtained from the average reward optimality equation are not only average reward optimal, but indeed sample path average reward optimal, for almost all sample paths.Research supported by a U.S.-México Collaborative Research Program funded by the National Science Foundation under grant NSF-INT 9201430, and by CONACyT-MEXICO.Partially supported by the MAXTOR Foundation for applied Probability and Statistics, under grant No. 01-01-56/04-93.Research partially supported by the Engineering Foundation under grant RI-A-93-10, and by a grant from the AT&T Foundation.     

A parameter-uniform Schwarz method for a coupled system of reaction–diffusion equations

We consider an arbitrarily sized coupled system of one-dimensional reaction–diffusion problems that are singularly perturbed in nature. We describe an algorithm that uses a discrete Schwarz method on three overlapping subdomains, extending the method in [H. MacMullen, J.J.H. Miller, E. O’Riordan, G.I. Shishkin, A second-order parameter-uniform overlapping Schwarz method for reaction-diffusion problems with boundary layers, J. Comput. Appl. Math. 130 (2001) 231–244] to a coupled system. On each subdomain we use a standard finite difference operator on a uniform mesh. We prove that when appropriate subdomains are used the method produces ε-uniform results. Furthermore we improve upon the analysis of the above-mentioned reference to show that, for small ε, just one iteration is required to achieve the expected accuracy.     

An M/M/1 Driven Fluid Queue – Continued Fraction Approach

This paper presents complete solutions of the stationary distributions of buffer occupancy and buffer content of a fluid queue driven by an M/M/1 queue. We assume a general boundary condition when compared to the model discussed in Virtamo and Norros [Queueing Systems 16 (1994) 373–386] and Adan and Resing [Queueing Systems 22 (1996) 171–174]. We achieve the required solutions by transforming the underlying system of differential equations using Laplace transforms to a system of difference equations leading to a continued fraction. This continued fraction helps us to find complete solutions. We also obtain the buffer content distribution for this fluid model using the method of Sericola and Tuffin [Queueing Systems 31 (1999) 253–264].     

Limit laws for the maximum and minimum of stationary sequences

Summary The class of non-degenerate joint limiting distributions for the maximum and minimum of stationary mixing sequences is determined. These limit distributions are of the form, H(x, ) –H(x, –y), where H(x,y) is a bivariate extreme value distribution. Unlike the classical result for i.i.d. sequences, the maximum and minimum of stationary mixing sequences may be asymptotically dependent. We also give a sufficient condition for the asymptotic independence of the maximum and minimum. Finally, an example of a stationary sequence satisfying the mixing condition D in Leadbetter but which is not weakly mixing is constructed.This research was supported in part by the National Science Foundation grant MCS 80-05483