Online time-constrained scheduling in linear and ring networks

We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002) [3]. In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios.     

考虑投资人过度自信偏好的占线股票投资策略研究

当股票价格及收益的统计信息不足或无法构建精确概率分布时,股票占线投资问题获得广泛关注,即投资人能够运用在线算法和竞争分析设计出更好的占线投资策略以应对股价的不确定性。本文将投资人过度自信偏好这种认知偏差,引入到股票占线投资问题中,构建了离线对手与股票占线投资人的博弈模型,分别给出一般情形和存在动量效应情形下的最优混合策略和混合策略纳什均衡。结果发现,两种情形下的最优混合策略不仅克服了传统股票投资策略对股价或股票收益概率分布假设的过度依赖,并且更好地抽象了股票占线投资人过度自信、追涨杀跌等特征,对现有行为金融与金融占线交易问题的研究提供了有益补充。     

Log-Optimal Portfolios with Memory Effect

ABSTRACT

In portfolio optimization a classical problem is to trade with assets so as to maximize some kind of utility of the investor. In our paper this problem is investigated for assets whose prices depend on their past values in a non-Markovian way. Such models incorporate several features of real price processes better than Markov processes do. Our utility function is the widespread logarithmic utility, the formulation of the model is discrete in time. Despite the problem being a well-known one, there are few results where memory is treated systematically in a parametric model. Our algorithm is optimal and this optimality is guaranteed for a rich class of model specifications. Moreover, the algorithm runs online, i.e., the optimal investment is achieved in a day-by-day manner, using simple numerical integration, without Monte-Carlo simulations. Theoretical results are demonstrated by numerical experiments as well.     

Analysis of queueing policies in QoS switches

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the “best effort” approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst-case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.     

Efficient offline algorithms for the bicriteria k-server problem and online applications

In this paper we consider the bicriteria version of the well-known k-server problem in which the cost incurred by an algorithm is evaluated simultaneously with respect to two different edge weightings.We show that it is possible to achieve the same competitive ratios of the previously known online algorithms with a dramatic improvement of the running time, i.e., from exponential to polynomial.Such results are obtained by exploiting new polynomial time algorithms able to find offline solutions whose costs differ from the optimal ones only of additive terms independent from the sequence of requests.     

统计信息下在线反向拍卖的竞争分析

对于投标具有统计特征的在线反向拍卖问题,利用在线算法与平均情形竞争分析相结合的方法,讨论了单一定价策略的平均情形最优单一定价及其竞争性能,提出了无限可分商品在线反向拍卖的平均情形竞争分析策略,基于此策略建立了具有均匀分布特征的在线反向拍卖模型,通过对模型求解得到了采购商的竞争需要曲线。与不考虑投标的统计信息、只是利用常规的最坏情形竞争分析得到的在线反向拍卖的竞争策略进行对比分析,发现统计信息的利用提高了在线反向拍卖策略的竞争性能。     

Improving solution of discrete competitive facility location problems

We consider discrete competitive facility location problems in this paper. Such problems could be viewed as a search of nodes in a network, composed of candidate and customer demand nodes, which connections correspond to attractiveness between customers and facilities located at the candidate nodes. The number of customers is usually very large. For some models of customer behavior exact solution approaches could be used. However, for other models and/or when the size of problem is too high to solve exactly, heuristic algorithms may be used. The solution of discrete competitive facility location problems using genetic algorithms is considered in this paper. The new strategies for dynamic adjustment of some parameters of genetic algorithm, such as probabilities for the crossover and mutation operations are proposed and applied to improve the canonical genetic algorithm. The algorithm is also specially adopted to solve discrete competitive facility location problems by proposing a strategy for selection of the most promising values of the variables in the mutation procedure. The developed genetic algorithm is demonstrated by solving instances of competitive facility location problems for an entering firm.     

Internet shopping with price sensitive discounts

A customer would like to buy a given set of products in a given set of Internet shops. For each Internet shop, standard prices for the products are known as well as a concave increasing discounting function of total standard and delivery price. The problem is to buy all the required products at the minimum total discounted price. Computational complexity of various special cases is established. Properties of optimal solutions are proved and polynomial time and exponential time solution algorithms based on these properties are designed. Two heuristic algorithms are suggested and computationally tested.     

Distributed Online Frequency Assignment in Cellular Networks

A cellular network is generally modeled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multicoloring problem on a weighted graph, where the weight vector associated with the vertices models the number of calls to be served at the vertices and is assumed to change over time. In this paper, we develop a framework for studying distributed online frequency assignment in cellular networks. We present the first distributed online algorithms for this problem with proven bounds on their competitive ratios. We show a series of algorithms that use at each vertex information about increasingly larger neighborhoods of the vertex, and that achieve better competitive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms.     

Online C-benevolent job scheduling on multiple machines

We consider scheduling a sequence of C-benevolent jobs on multiple homogeneous machines. For two machines, we propose a 2-competitive Cooperative Greedy algorithm and provide a lower bound of 2 for the competitive ratio of any deterministic online scheduling algorithms on two machines. For multiple machines, we propose a Pairing-m Greedy algorithm, which is deterministic 2-competitive for even number of machines and randomized \((2+2/{\hbox {m}})\)-competitive for odd number of machines. We provide a lower bound of 1.436 for the competitive ratio of any deterministic online scheduling algorithms on three machines, which is the best known lower bound for competitive ratios of deterministic scheduling algorithms on three machines.     

Determining optimal selling price and lot size with a varying rate of deterioration and exponential partial backlogging

In this paper, a deterministic inventory model for deteriorating items with price-dependent demand is developed. The demand and deterioration rates are continuous and differentiable function of price and time, respectively. In addition, we allow for shortages and the unsatisfied demand is partially backlogged at a negative exponential rate with the waiting time. Under these assumptions, for any given selling price, we first develop the criterion for the optimal solution for the replenishment schedule, and prove that the optimal replenishment policy not only exists but also is unique. If the criterion is not satisfied, the inventory system should not be operated. Next, we show that the total profit per unit time is a concave function of price when the replenishment schedule is given. We then provide a simple algorithm to find the optimal selling price and replenishment schedule for the proposed model. Finally, we use numerical examples to illustrate the algorithm.     

Competitive analysis of price online inventory problem with cost function

In this paper, a new price is given to the online decision maker at the beginning of each day. The trader must decide how many items to purchase according to the current price. We present three variants and an online algorithm based on cost function. The competitive ratio of the online algorithm is given for each variant, which is a performance measure of an online algorithm. More importantly, we show that the online algorithm is optimal.     

Multi-parameter Tikhonov regularization and model function approach to the damped Morozov principle for choosing regularization parameters

In this paper, we study the multi-parameter Tikhonov regularization method which adds multiple different penalties to exhibit multi-scale features of the solution. An optimal error bound of the regularization solution is obtained by a priori choice of multiple regularization parameters. Some theoretical results of the regularization solution about the dependence on regularization parameters are presented. Then, an a posteriori parameter choice, i.e., the damped Morozov discrepancy principle, is introduced to determine multiple regularization parameters. Five model functions, i.e., two hyperbolic model functions, a linear model function, an exponential model function and a logarithmic model function, are proposed to solve the damped Morozov discrepancy principle. Furthermore, four efficient model function algorithms are developed for finding reasonable multiple regularization parameters, and their convergence properties are also studied. Numerical results of several examples show that the damped discrepancy principle is competitive with the standard one, and the model function algorithms are efficient for choosing regularization parameters.     

Online scheduling with general machine cost functions

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently online scheduling problems have been investigated with the modification that initially the algorithm possesses no machines, but that at any point additional machines may be purchased. In all of these models the assumption has been made that each machine has unit cost. In this paper we consider the problem with general machine cost functions. Furthermore we also consider a more general version of the problem where the available machines have speed, the algorithm may purchase machines with speed 1 and machines with speed s. We define and analyze some algorithms for the solution of these problems and their special cases. Moreover we prove some lower bounds on the possible competitive ratios.     

退款保证对竞争供应链的影响:基于顾客退货行为视角

为研究退款保证对竞争供应链的影响,从顾客退货行为视角构建消费者效用函数,建立竞争制造商与在线零售商之间的博弈模型,分析退款保证对供应链均衡的影响。研究发现:高质量产品的批发价格和零售价格总是更高,但高质量产品制造商可能并不能获得更多利润;退款保证会影响消费者的产品购买选择,对低质量产品需求有利。然而,从利润最大化的角度,在线零售商只有在退货损失足够低时,才会有动机提供退款保证,而退款保证对制造商利润的影响取决于退货产品残值。     

基于指数分布的可恢复加拿大旅行者问题的策略研究

针对旅行者在行走过程中遇到的某一或一系列无法预知堵塞事件的加拿大旅行者问题,考虑每个堵塞恢复时间是一个相互独立随机变量且服从指数分布的情形,从在线问题与竞争策略的角度,给出了等待策略和贪婪策略以及相应策略下的竞争比,并对两种策略的执行效果进行了分析和比较.     

一种电子商务环境下耐用品的动态定价模型与策略

针对电子商务环境下消费者对价格歧视的抗拒问题,以及耐用品生命周期长、产品需求依赖于时间、价格等特点,提出了一种动态定价模型与策略。该模型通过构造转移概率矩阵,推导出在线消费者浏览到耐用品的不同价格状态下的概率,接着根据消费者多阶段效用函数分析消费者的购买决策行为,进而给出零售商利润达到最大化时的最优定价策略集合。为了验证模型与策略的有效性,通过数值模拟实验,分析模型主要参数变化对最优定价策略的影响。研究发现当效用折扣因子越高,零售商应该降低促销频率和高价格并且提高低价格,从而诱导高端消费者在高价格购买产品。折扣效用因子大小还决定了网上零售商是否要隐藏自己的促销概率。     

Estimating intermediate price transitions in online auctions

This paper discusses a statistical model regarding intermediate price transitions of online auctions. The objective was to characterize the stochastic process by which prices of online auctions evolve and to estimate conditional intermediate price transition probabilities given current price, elapsed auction time, number of competing auctions, and calendar time. Conditions to ensure monotone price transitions in the current price and number of competing auctions are discussed and empirically validated. In particular, we show that over discrete periods, the intermediate price transitions are increasing in the current price, decreasing in the number of ongoing auctions at a diminishing rate, and decreasing over time. These results provide managerial insight into the effect of how online auctions are released and overlap. The proposed model is based on the framework of generalized linear models using a zero‐inflated gamma distribution. Empirical analysis and parameter estimation is based on data from eBay auctions conducted by Dell. Copyright © 2011 John Wiley & Sons, Ltd.     

Passport options with stochastic volatility

A passport option is a call option on the profits of a trading account. In this article, the robustness of passport option pricing is investigated by incorporating stochastic volatility. The key feature of a passport option is the holders' optimal strategy. It is known that in the case of exponential Brownian motion the strategy is to be long if the trading account is below zero and short if the account is above zero. Here this result is extended to models with stochastic volatility where the volatility is defined via an autonomous SDE. It is shown that if the Brownian motions driving the underlying asset and the volatility are independent then the form of the optimal strategy remains unchanged. This means that the strategy is robust to misspecification of the underlying model. A second aim of this article is to investigate some of the biases which become apparent in a stochastic volatility regime. Using an analytic approximation, comparisons are obtained for passport option prices using the exponential Brownian motion model and some well-known stochastic volatility models. This is illustrated with numerical examples. One conclusion is that if volatility and price are uncorrelated, then prices are sometimes lower in a model with stochastic volatility than in a model with constant volatility.     

国际原油价格预测的双层随机整数规划模型、算法及应用

根据国际原油价格近期数据及原油价格变化量,给出了国际原油价格改变量的状态转移概率(或频率)矩阵.依此提出以国际原油价格预测误差的期望与方差最小为最优目标,建立国际原油价格预测的双层随机整数规划,并论述该优化问题最优解的存在性, 根据约束特性构造了优化算法.同时按照国内现行成品油定价机制, 提出的优化算法,对国内成品油调价进行了预测,实证分析表明提出的模型与优化算法具有一定的预测精度和较好的实用性.