In this work we investigate the portfolio selection problem (P1) and bi-directional trading (P2) when prices are interrelated. Zhang et al. (J. Comb. Optim. 23 (2012) 159-166) provided the algorithm UND which solves o...
详细信息
In this work we investigate the portfolio selection problem (P1) and bi-directional trading (P2) when prices are interrelated. Zhang et al. (J. Comb. Optim. 23 (2012) 159-166) provided the algorithm UND which solves one variant of P2. We are interested in solutions which are optimal from a worst-case perspective. For P1, we prove the worst-case input sequence and derive the algorithm optimal portfolio for interrelated prices (OPIP). We then prove the competitive ratio and optimality. We use the idea of OPIP to solve P2 and derive the algorithm called optimal conversion for interrelated prices (OCIP). Using OCIP, we also design optimal online algorithms for bi-directional search (P3) called bi-directional UND (BUND) and optimal online search for unknown relative price bounds (RUN). We run numerical experiments and conclude that OPIP and OCIP perform well compared to other algorithms even if prices do not behave adverse.
We study parallel online algorithms: For some fixed integer k, a collective of k parallel processes that perform online decisions on the same sequence of events forms a k-copy algorithm. For any given time and input s...
详细信息
We study parallel online algorithms: For some fixed integer k, a collective of k parallel processes that perform online decisions on the same sequence of events forms a k-copy algorithm. For any given time and input sequence, the overall performance is determined by the best of the k individual total results. Problems of this type have been considered for online makespan minimization;they are also related to optimization with advice on future events, i.e., a number of bits available in advance. Parallel online algorithms are also of interest in practical scenarios in which redundancy is used for hedging against undesired outcomes. We develop PREDICTIVE HARMONIC(3) (PH3), a relatively simple family of k-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing k. In particular, we show that k = 6 suffices to guarantee a factor of 1.5714 for PH3, which is better than 1.57829, the performance of the best known 1-copy algorithm ADVANCED HARMONIC, while k = 11 suffices to achieve a factor of 1.5406, beating the known lower bound of 1.54278 for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of 1.54278, which is considerably less than the previous bound of 15 bits.
We consider the model of online computation with advice (Emek et al., Theor. Comput. Sci. 412(24): 2642-2656, 2011). In particular, we study the k-server problem under this model. We prove three upper bounds for this ...
详细信息
We consider the model of online computation with advice (Emek et al., Theor. Comput. Sci. 412(24): 2642-2656, 2011). In particular, we study the k-server problem under this model. We prove three upper bounds for this problem. First, we show a -competitive online algorithm for general metric spaces with b bits of advice per request, where 3a parts per thousand currency signba parts per thousand currency signlogk. This improves upon the result of Bockenhauer et al. (ICALP (1), Lecture Notes in Computer Science, vol. 6755, pp. 207-218, 2011). Moreover, we believe that our algorithm and our analysis are more intuitive and simpler than those of Bockenhauer et al. Second, we give a 1-competitive online algorithm for finite trees which uses 2+2aOElog(p+1)aOE parts per thousand bits of advice per request, where p is the caterpillar dimension of the tree. Lastly, we present a variant of the algorithm for the tree that is optimal for the line with 1-bit of advice.
Reliability control is a key concern on the evolution of mobile multicast services. To this direction, the use of forward error correction (FEC) on the application layer is widely adopted in several mobile multicast s...
详细信息
Reliability control is a key concern on the evolution of mobile multicast services. To this direction, the use of forward error correction (FEC) on the application layer is widely adopted in several mobile multicast standards. FEC is a feedback free error control method, where the transmitter introduces in advance redundant information within the source data to enable receivers recovering arbitrary data erasures. On multicast delivery where retransmission-based error recovery methods are not efficient, the most suitable error control method is the use of application layer forward error correction (AL-FEC) codes. In this work, we introduce novel AL-FEC deployment policies over mobile multicast environments utilizing online algorithms. We aim at the efficient application of AL-FEC protection with RaptorQ codes over multicast delivery in the context of competitive analysis. We provide a competitiveness analysis model of AL-FEC application over mobile multicast environments. Furthermore, we propose two online algorithms adjusting the introduced redundancy of AL-FEC protection according to several FEC encoding parameters and constraints of mobile multicast delivery.
We consider one-by-one online scheduling on uniformly related machines. The input is a sequence of machines with different speeds and a sequence of jobs with different processing times. The output is a schedule which ...
详细信息
We consider one-by-one online scheduling on uniformly related machines. The input is a sequence of machines with different speeds and a sequence of jobs with different processing times. The output is a schedule which assigns the jobs to the machines;the completion time of a machine is the sum of the processing times of jobs assigned to it divided by its speed. The objective is to minimize the maximal completion time. The jobs arrive one by one and each has to be assigned to one machine immediately and irrevocably without the knowledge of the future jobs. We prove a new lower bound of 2.564 on the competitive ratio of deterministic online algorithms for this problem, improving the previous lower bound of 2.438.
We introduce a new technique for the analysis of online algorithms, namely bijective analysis, that is based on pair-wise comparison of the costs incurred by the algorithms. Under this framework, an algorithm A is no ...
详细信息
We introduce a new technique for the analysis of online algorithms, namely bijective analysis, that is based on pair-wise comparison of the costs incurred by the algorithms. Under this framework, an algorithm A is no worse than an algorithm B if there is a bijection defined over all request sequences of a given size such that the cost of A on sigma is no more than the cost of B on B((sigma)). We also study a relaxation of bijective analysis, termed average analysis, in which we compare two algorithms based on their corresponding average costs over request sequences of a given size. We apply these new techniques in the context of two fundamental online problems, namely paging and list update. For paging, we show that any two lazy online algorithms are equivalent under bijective analysis. This result demonstrates that, without further assumptions on characteristics of request sequences, it is unlikely, or even undesirable, to separate online paging algorithms based on their performance. However, once we restrict the set of request sequences to those exhibiting locality of reference, and in particular using a model of locality due to Albers et al. (J Comput Syst Sci 70(2):145-175, 2005), we demonstrate that Least-Recently-Used (LRU) is the unique optimal strategy according to average analysis. This is, to our knowledge, the first deterministic model to provide full theoretical backing to the empirical observation that LRU is preferable in practice. Concerning list update, we obtain similar conclusions, in terms of the bijective comparison of any two online algorithms, and in terms of the superiority (albeit not necessarily unique) of the Move-To-Front (MTF) heuristic in the presence of locality of reference.
A class of "simple" online algorithms for the k-server problem is identified. This class, for which the term trackless is introduced, includes many known server algorithms. The k-server conjecture fails for ...
详细信息
A class of "simple" online algorithms for the k-server problem is identified. This class, for which the term trackless is introduced, includes many known server algorithms. The k-server conjecture fails for trackless algorithms. A lower bound of 23/11 on the competitiveness of any deterministic trackless 2-server algorithm and a lower bound of 1 + root 2/2 on the competitiveness of any randomized trackless 2-server problem are given. (C) 2000 Published by Elsevier Science B.V. An rights reserved.
Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient ''simulation'' of randomized on-line algorithms ...
详细信息
Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient ''simulation'' of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.
We study online preemptive makespan minimization on m parallel machines, where multiprocessor jobs arrive over time and have widths (i.e., the number of machines used) from some fixed set W subset of {1, 2, ..., m}. F...
详细信息
We study online preemptive makespan minimization on m parallel machines, where multiprocessor jobs arrive over time and have widths (i.e., the number of machines used) from some fixed set W subset of {1, 2, ..., m}. For every number m of machines we concisely characterize all the sets W for which there exists a 1-competitive fully online algorithm and all the sets W for which there is a 1-competitive nearly online algorithm.(c) 2023 Elsevier B.V. All rights reserved.
An efficient randomized online algorithm for the paging problem for cache size 2 is given, which is 3/2-competitive against an oblivious adversary. The algorithm keeps track of at most one page in slow memory at any t...
详细信息
An efficient randomized online algorithm for the paging problem for cache size 2 is given, which is 3/2-competitive against an oblivious adversary. The algorithm keeps track of at most one page in slow memory at any time. A lower bound of 37/24 approximate to 1.5416 is given for the competitiveness of any trackless online algorithm for the same problem, i.e., an algorithm that keeps track of no page outside the cache. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论