Journal articles: 'Competitive online algorithms'

1

Wu, Yonghua, Guohun Zhu, Huaying Chen, and Jucun Qin. "WIN Algorithm for Discrete Online TSP." Journal of Advanced Computational Intelligence and Intelligent Informatics 15, no. 9 (November 20, 2011): 1199–202. http://dx.doi.org/10.20965/jaciii.2011.p1199.

Full text

Abstract:

Traveling Salesman Problem (TSP) which is proved as an NP-Complete problem is solved by many algorithms. In this paper, we propose online TSP which is based on general discrete metric space. A Waiting-If-Necessary (WIN) algorithm is proposed that involves with increasing cost caused by zealous algorithms and unnecessary waiting caused by cautious algorithms. We measure the performance of the WIN algorithm using competitive analysis and found that it is a 2-competitive algorithm. The competitive ratio of theWIN algorithm can be improved by setting parameterT0.

APA, Harvard, Vancouver, ISO, and other styles

2

ZHANG, YONG, YUXIN WANG, FRANCIS Y. L. CHIN, and HING-FUNG TING. "COMPETITIVE ALGORITHMS FOR ONLINE PRICING." Discrete Mathematics, Algorithms and Applications 04, no. 02 (June 2012): 1250015. http://dx.doi.org/10.1142/s1793830912500152.

Full text

Abstract:

Given a seller with m items, a sequence of users {u1, u2, …} come one by one, the seller must set the unit price and assign some items to each user on his/her arrival. Items can be sold fractionally. Each ui has his/her value function vi(⋅) such that vi(x) is the highest unit price ui is willing to pay for x items. The objective is to maximize the revenue by setting the price and number of items for each user. In this paper, we have the following contributions: if the highest value h among all vi(x) is known in advance, we first show the lower bound of the competitive ratio is ⌊ log h⌋/2, then give an online algorithm with competitive ratio 4⌊ log h⌋ + 6; if h is not known in advance, we give an online algorithm with competitive ratio 2⋅h log -1/2 h + 8⋅h3 log -1/2 h.

APA, Harvard, Vancouver, ISO, and other styles

3

Kumar, Sandeep, and Deepak Garg. "Online Financial Algorithms: Competitive Analysis." International Journal of Computer Applications 40, no. 7 (February 29, 2012): 8–14. http://dx.doi.org/10.5120/4974-7228.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Ashlagi, Itai, Brendan Lucier, and Moshe Tennenholtz. "Equilibria of Online Scheduling Algorithms." Proceedings of the AAAI Conference on Artificial Intelligence 27, no. 1 (June 30, 2013): 67–73. http://dx.doi.org/10.1609/aaai.v27i1.8631.

Full text

Abstract:

We describe a model for competitive online scheduling algorithms. Two servers, each with a single observable queue, compete for customers. Upon arrival, each customer strategically chooses the queue with minimal expected wait time. Each scheduler wishes to maximize its number of customers, and can strategically select which scheduling algorithm, such as First-Come-First-Served (FCFS), to use for its queue. This induces a game played by the servers and the customers. We consider a non-Bayesian setting, where servers and customers play to maximize worst-case payoffs. We show that there is a unique subgame perfect safety-level equilibrium and we describe the associated scheduling algorithm (which is not FCFS). The uniqueness result holds for both randomized and deterministic algorithms, with a different equilibrium algorithm in each case. When the goal of the servers is to minimize competitive ratio, we prove that it is an equilibrium for each server to apply FCFS: each server obtains the optimal competitive ratio of 2.

APA, Harvard, Vancouver, ISO, and other styles

5

Hopf, Michael, Clemens Thielen, and Oliver Wendt. "Competitive algorithms for multistage online scheduling." European Journal of Operational Research 260, no. 2 (July 2017): 468–81. http://dx.doi.org/10.1016/j.ejor.2016.12.047.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Yang, Lin, Ali Zeynali, Mohammad H. Hajiesmaili, Ramesh K. Sitaraman, and Don Towsley. "Competitive Algorithms for Online Multidimensional Knapsack Problems." Proceedings of the ACM on Measurement and Analysis of Computing Systems 5, no. 3 (December 14, 2021): 1–30. http://dx.doi.org/10.1145/3491042.

Full text

Abstract:

In this paper, we study the online multidimensional knapsack problem (called OMdKP) in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and m-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem and finds several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop two algorithms for OMdKP that use linear and exponential reservation functions to make online admission decisions. Our competitive analysis shows that the linear and exponential algorithms achieve the competitive ratios of O(θα ) and O(łogł(θα)), respectively, where α is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and θ is the ratio between the maximum and minimum item unit values. We also characterize a lower bound for the competitive ratio of any online algorithm solving OMdKP and show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.

APA, Harvard, Vancouver, ISO, and other styles

7

Lee, Russell, Jessica Maghakian, Mohammad Hajiesmaili, Jian Li, Ramesh Sitaraman, and Zhenhua Liu. "Online peak-aware energy scheduling with untrusted advice." ACM SIGEnergy Energy Informatics Review 1, no. 1 (November 2021): 59–77. http://dx.doi.org/10.1145/3508467.3508473.

Full text

Abstract:

This paper studies the online energy scheduling problem in a hybrid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the proposed algorithms using two performance metrics: robustness that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and consistency for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimality of the proposed algorithms. Our results show that the proposed deterministic algorithm is Pareto-optimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Pareto-optimal deterministic algorithm. Our large-scale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms outperform worst-case optimized algorithms and fully data-driven algorithms.

APA, Harvard, Vancouver, ISO, and other styles

8

Xu, Chenyang, and Benjamin Moseley. "Learning-Augmented Algorithms for Online Steiner Tree." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 8 (June 28, 2022): 8744–52. http://dx.doi.org/10.1609/aaai.v36i8.20854.

Full text

Abstract:

This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm’s worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms’ performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.

APA, Harvard, Vancouver, ISO, and other styles

9

Ma, Hang. "A Competitive Analysis of Online Multi-Agent Path Finding." Proceedings of the International Conference on Automated Planning and Scheduling 31 (May 17, 2021): 234–42. http://dx.doi.org/10.1609/icaps.v31i1.15967.

Full text

Abstract:

We study online Multi-Agent Path Finding (MAPF), where new agents are constantly revealed over time and all agents must find collision-free paths to their given goal locations. We generalize existing complexity results of (offline) MAPF to online MAPF. We classify online MAPF algorithms into different categories based on (1) controllability (the set of agents that they can plan paths for at each time) and (2) rationality (the quality of paths they plan) and study the relationships between them. We perform a competitive analysis for each category of online MAPF algorithms with respect to commonly-used objective functions. We show that a naive algorithm that routes newly-revealed agents one at a time in sequence achieves a competitive ratio that is asymptotically bounded from both below and above by the number of agents with respect to flowtime and makespan. We then show a counter-intuitive result that, if rerouting of previously-revealed agents is not allowed, any rational online MAPF algorithms, including ones that plan optimal paths for all newly-revealed agents, have the same asymptotic competitive ratio as the naive algorithm, even on 2D 4-neighbor grids. We also derive constant lower bounds on the competitive ratio of any rational online MAPF algorithms that allow rerouting. The results thus provide theoretical insights into the effectiveness of using MAPF algorithms in an online setting for the first time.

APA, Harvard, Vancouver, ISO, and other styles

10

Yang, Lin, Ali Zeynali, Mohammad H. Hajiesmaili, Ramesh K. Sitaraman, and Don Towsley. "Competitive Algorithms for Online Multidimensional Knapsack Problems." ACM SIGMETRICS Performance Evaluation Review 50, no. 1 (June 20, 2022): 87–88. http://dx.doi.org/10.1145/3547353.3522627.

Full text

Abstract:

In this work, we study the online multidimensional knapsack problem (called OMdKP) in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and m-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem with several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop an online algorithm for OMdKP that uses an exponential reservation function to make online admission decisions. Our competitive analysis shows that the proposed online algorithm achieves the competitive ratio of O(log (Θ α)), where α is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and θ is the ratio between the maximum and minimum item unit values. We also show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor.

APA, Harvard, Vancouver, ISO, and other styles

11

Chen, Lin, Deshi Ye, and Guochuan Zhang. "Approximating the Optimal Algorithm for Online Scheduling Problems via Dynamic Programming." Asia-Pacific Journal of Operational Research 32, no. 01 (February 2015): 1540011. http://dx.doi.org/10.1142/s0217595915400114.

Full text

Abstract:

Very recently Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] initiate a new systematic way of studying online problems by introducing the competitive ratio approximation scheme (simplified as competitive schemes in this paper), which is a class of algorithms {Aϵ|ϵ > 0} with a competitive ratio at most ρ*(1 + ϵ), where ρ* is the best possible competitive ratio over all online algorithms. Along this line, Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] provide competitive schemes for several online over time scheduling problems like Qm|rj, (pmtn)|∑wjcj, while the running times are polynomial if the number of machines is a constant. In this paper, we consider the classical online scheduling problems, where jobs arrive in a list. We present competitive schemes for Rm‖C max and [Formula: see text], where the running times are polynomial if the number of machines is a constant. Specifically, we are able to derive a competitive scheme for P‖C max which runs in polynomial time even if the number of machines is an input. Our method is novel and more efficient than that of Günther et al. [E. Günther, O. Maurer, N. Megow and A. Wiese (2013). A new approach to online scheduling: Approximating the optimal competitive ratio. In Proc. 24th Annual ACM-SIAM Symp. Discrete Algorithms (SODA).] Indeed, by utilizing the standard rounding technique for the off-line scheduling problems, we reformulate the online scheduling problem into a game on an infinite graph, through which we arrive at the following key point: Assuming that the best competitive ratio is ρ*, for any online algorithm there exists a list of a polynomial number of jobs showing that its competitive ratio is at least ρ* - O(ϵ). Interestingly such a result is achieved via a dynamic programming algorithm. Our framework is also applicable to other online problems.

APA, Harvard, Vancouver, ISO, and other styles

12

BOSE, PROSENJIT, ANDREJ BRODNIK, SVANTE CARLSSON, ERIK D. DEMAINE, RUDOLF FLEISCHER, ALEJANDRO LÓPEZ-ORTIZ, PAT MORIN, and J. IAN MUNRO. "ONLINE ROUTING IN CONVEX SUBDIVISIONS." International Journal of Computational Geometry & Applications 12, no. 04 (August 2002): 283–95. http://dx.doi.org/10.1142/s021819590200089x.

Full text

Abstract:

We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation.

APA, Harvard, Vancouver, ISO, and other styles

13

Likas, Aristidis. "A Reinforcement Learning Approach to Online Clustering." Neural Computation 11, no. 8 (November 1, 1999): 1915–32. http://dx.doi.org/10.1162/089976699300016025.

Full text

Abstract:

A general technique is proposed for embedding online clustering algorithms based on competitive learning in a reinforcement learning framework. The basic idea is that the clustering system can be viewed as a reinforcement learning system that learns through reinforcements to follow the clustering strategy we wish to implement. In this sense, the reinforcement guided competitive learning (RGCL) algorithm is proposed that constitutes a reinforcement-based adaptation of learning vector quantization (LVQ) with enhanced clustering capabilities. In addition, we suggest extensions of RGCL and LVQ that are characterized by the property of sustained exploration and significantly improve the performance of those algorithms, as indicated by experimental tests on well-known data sets.

APA, Harvard, Vancouver, ISO, and other styles

14

Buchbinder, Niv, Shahar Chen, Joseph (Seffi) Naor, and Ohad Shamir. "Unified Algorithms for Online Learning and Competitive Analysis." Mathematics of Operations Research 41, no. 2 (May 2016): 612–25. http://dx.doi.org/10.1287/moor.2015.0742.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

HE, YONG, SHUGUANG HAN, and YIWEI JIANG. "ONLINE ALGORITHMS FOR SCHEDULING WITH MACHINE ACTIVATION COST." Asia-Pacific Journal of Operational Research 24, no. 02 (April 2007): 263–77. http://dx.doi.org/10.1142/s0217595907001231.

Full text

Abstract:

In this paper, we consider a variant of the classical parallel machine scheduling problem. For this problem, we are given m potential identical machines to non-preemptively process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and activation cost of machines. We first present two optimal online algorithms with competitive ratios of 3/2 and 5/3 for m = 2, 3 cases, respectively. Then we present an online algorithm with a competitive ratio of at most 2 for general m ≥ 4, while the lower bound is 1.88.

APA, Harvard, Vancouver, ISO, and other styles

16

Barrière, Lali, Xavier Muñoz, Janosch Fuchs, and Walter Unger. "Online Matching in Regular Bipartite Graphs." Parallel Processing Letters 28, no. 02 (June 2018): 1850008. http://dx.doi.org/10.1142/s0129626418500081.

Full text

Abstract:

In an online problem, the input is revealed one piece at a time. In every time step, the online algorithm has to produce a part of the output, based on the partial knowledge of the input. Such decisions are irrevocable, and thus online algorithms usually lead to nonoptimal solutions. The impact of the partial knowledge depends strongly on the problem. If the algorithm is allowed to read binary information about the future, the amount of bits read that allow the algorithm to solve the problem optimally is the so-called advice complexity. The quality of an online algorithm is measured by its competitive ratio, which compares its performance to that of an optimal offline algorithm. In this paper we study online bipartite matchings focusing on the particular case of bipartite matchings in regular graphs. We give tight upper and lower bounds on the competitive ratio of the online deterministic bipartite matching problem. The competitive ratio turns out to be asymptotically equal to the known randomized competitive ratio. Afterwards, we present an upper and lower bound for the advice complexity of the online deterministic bipartite matching problem.

APA, Harvard, Vancouver, ISO, and other styles

17

Du, Bingqian, Zhiyi Huang, and Chuan Wu. "Adversarial Deep Learning for Online Resource Allocation." ACM Transactions on Modeling and Performance Evaluation of Computing Systems 6, no. 4 (December 31, 2021): 1–25. http://dx.doi.org/10.1145/3494526.

Full text

Abstract:

Online algorithms are an important branch in algorithm design. Designing online algorithms with a bounded competitive ratio (in terms of worst-case performance) can be hard and usually relies on problem-specific assumptions. Inspired by adversarial training from Generative Adversarial Net and the fact that the competitive ratio of an online algorithm is based on worst-case input, we adopt deep neural networks (NNs) to learn an online algorithm for a resource allocation and pricing problem from scratch, with the goal that the performance gap between offline optimum and the learned online algorithm can be minimized for worst-case input. Specifically, we leverage two NNs as the algorithm and the adversary, respectively, and let them play a zero sum game, with the adversary being responsible for generating worst-case input while the algorithm learns the best strategy based on the input provided by the adversary. To ensure better convergence of the algorithm network (to the desired online algorithm), we propose a novel per-round update method to handle sequential decision making to break complex dependency among different rounds so that update can be done for every possible action instead of only sampled actions. To the best of our knowledge, our work is the first using deep NNs to design an online algorithm from the perspective of worst-case performance guarantee. Empirical studies show that our updating methods ensure convergence to Nash equilibrium and the learned algorithm outperforms state-of-the-art online algorithms under various settings.

APA, Harvard, Vancouver, ISO, and other styles

18

Dwibedy, Debasis, and Rakesh Mohanty. "Online List Scheduling for Makespan Minimization." ACM SIGACT News 53, no. 2 (June 10, 2022): 84–105. http://dx.doi.org/10.1145/3544979.3544993.

Full text

Abstract:

In the modern interactive computing era, computational problems such as scheduling, rout- ing, sequencing, and resource management are online in nature. In the online framework, at the outset, an algorithm receives and processes inputs one by one in order without the knowledge of future inputs, unlike in an offline framework, where an algorithm knows the entire input sequence at the beginning. The design of mathematical models and efficient al- gorithms for the online framework constitutes a challenging and competitive area of research in Theoretical Computer Science. The researchers have considered competitive analysis as a well-de ned and standard method to measure the performance of online algorithms.

APA, Harvard, Vancouver, ISO, and other styles

19

Goyal, Shashank, and Diwakar Gupta. "The Online Reservation Problem." Algorithms 13, no. 10 (September 23, 2020): 241. http://dx.doi.org/10.3390/a13100241.

Full text

Abstract:

Many sharing-economy platforms operate as follows. Owners list the availability of resources, prices, and contract-length limits. Customers propose contract start times and lengths. The owners decide immediately whether to accept or decline each proposal, even if the contract is for a future date. Accepted proposals generate revenue. Declined proposals are lost. At any decision epoch, the owner has no information regarding future proposals. The owner seeks easy-to-implement algorithms that achieve the best competitive ratio (CR). We first derive a lower bound on the CR of any algorithm. We then analyze CRs of all intuitive “greedy” algorithms. We propose two new algorithms that have significantly better CRs than that of any greedy algorithm for certain parameter-value ranges. The key idea behind these algorithms is that owners may reserve some amount of capacity for late-arriving higher-value proposals in an attempt to improve revenue. Our contribution lies in operationalizing this idea with the help of algorithms that utilize thresholds. Moreover, we show that if non-optimal thresholds are chosen, then those may lead to poor CRs. We provide a rigorous method by which an owner can decide the best approach in their context by analyzing the CRs of greedy algorithms and those proposed by us.

APA, Harvard, Vancouver, ISO, and other styles

20

FUNG, STANLEY P. Y., FRANCIS Y. L. CHIN, and HONG SHEN. "ONLINE SCHEDULING OF UNIT JOBS WITH BOUNDED IMPORTANCE RATIO." International Journal of Foundations of Computer Science 16, no. 03 (June 2005): 581–98. http://dx.doi.org/10.1142/s0129054105003170.

Full text

Abstract:

We consider the following online scheduling problem. We are given a set of jobs, each having an integral release time and deadline, unit processing length, and a nonnegative real weight. In each time unit one job is to be scheduled, and the objective is to maximize the total value (weight) obtained by scheduling the jobs. This problem arises in the scheduling of packets in network switches supporting quality-of-service (QoS). Previous algorithms for this problem are 2-competitive. In this paper we propose a new algorithm that achieves an improved competitive ratio when the importance ratio is bounded. Specifically, for job weights within the range [1..B], our algorithm is 2 - 1/(⌈ lg B⌉ + 2)-competitive, and the bound is tight.

APA, Harvard, Vancouver, ISO, and other styles

21

Lin, Qiulin, Yanfang Mo, Junyan Su, and Minghua Chen. "Competitive Online Optimization with Multiple Inventories." ACM SIGMETRICS Performance Evaluation Review 50, no. 1 (June 20, 2022): 83–84. http://dx.doi.org/10.1145/3547353.3530969.

Full text

Abstract:

We study an online inventory trading problem where a user seeks to maximize the aggregate revenue of trading multiple inventories over a time horizon. The trading constraints and concave revenue functions are revealed sequentially in time, and the user needs to make irrevocable decisions. The problem has wide applications in various engineering domains. Existing works employ the primal-dual framework to design online algorithms with sub-optimal, albeit near-optimal, competitive ratios (CR). We exploit the problem structure to develop a new divide-and-conquer approach to solve the online multi-inventory problem by solving multiple calibrated single-inventory ones separately and combining their solutions. The approach achieves the optimal CR of $łn θ + 1$ if $Nłeq łn θ + 1$, where N is the number of inventories and θ represents the revenue function uncertainty; it attains a CR of $1/[1-e^-1/(łnθ+1) ] \in [łn θ +1, łn θ +2)$ otherwise. The divide-and-conquer approach reveals novel structural insights for the problem, (partially) closes a gap in existing studies, and generalizes to broader settings. For example, it gives an algorithm with a CR within a constant factor to the lower bound for a generalized one-way trading problem with price elasticity with no previous results. When developing the above results, we also extend a recent CR-Pursuit algorithmic framework and introduce an online allocation problem with allowance augmentation, both of which can be of independent interest.

APA, Harvard, Vancouver, ISO, and other styles

22

Zhou, Hao, Ping Zhou, and Yiwei Jiang. "Improved Algorithms for Online Scheduling of Malleable Parallel Jobs on Two Identical Machines." Asia-Pacific Journal of Operational Research 32, no. 05 (October 2015): 1550034. http://dx.doi.org/10.1142/s0217595915500347.

Full text

Abstract:

This paper addresses online scheduling of malleable parallel jobs to minimize the maximum completion time, i.e., makespan. It is assumed that the execution time of a job Jj with processing time pj is pj/k + (k-1)c if the job is assigned to k machines, where c > 0 is a constant setup time. We consider online algorithms for the scheduling problem on two identical machines. Namely, the job Jj can be processed on one machine with execution time pj or alternatively two machines in parallel with execution time pj/2+c. For the asymptotical competitive ratio, we provide an improved online algorithm with makespan no more than (3/2)C* +c/2, where C* is the optimal makespan. For the strict competitive ratio, we propose an online algorithm with competitive ratio of 1.54, which is close to the lower bound of 1.5.

APA, Harvard, Vancouver, ISO, and other styles

23

Li, Wenjie, and Jinjiang Yuan. "An Improved Online Algorithm for the Online Preemptive Scheduling of Equal-Length Intervals on a Single Machine with Lookahead." Asia-Pacific Journal of Operational Research 32, no. 06 (December 2015): 1550047. http://dx.doi.org/10.1142/s0217595915500475.

Full text

Abstract:

This paper studies the online preemptive scheduling of equal-length intervals on a single machine with lookahead. Let [Formula: see text] be the length (processing time) of all intervals. In the problem, at every time point [Formula: see text], online algorithms can foresee all the intervals that will arrive in the time segment [Formula: see text] for a certain [Formula: see text]. When [Formula: see text], Zheng et al. [Comput- ers & Operations Research, 2013] established a lower bound of [Formula: see text] and provided an online algorithm with a competitive ratio of 3. In this paper, we provide for this problem an improved online algorithm with a competitive ratio of 2.

APA, Harvard, Vancouver, ISO, and other styles

24

Lykouris, Thodoris, and Sergei Vassilvitskii. "Competitive Caching with Machine Learned Advice." Journal of the ACM 68, no. 4 (July 7, 2021): 1–25. http://dx.doi.org/10.1145/3447579.

Full text

Abstract:

Traditional online algorithms encapsulate decision making under uncertainty, and give ways to hedge against all possible future events, while guaranteeing a nearly optimal solution, as compared to an offline optimum. On the other hand, machine learning algorithms are in the business of extrapolating patterns found in the data to predict the future, and usually come with strong guarantees on the expected generalization error. In this work, we develop a framework for augmenting online algorithms with a machine learned predictor to achieve competitive ratios that provably improve upon unconditional worst-case lower bounds when the predictor has low error. Our approach treats the predictor as a complete black box and is not dependent on its inner workings or the exact distribution of its errors. We apply this framework to the traditional caching problem—creating an eviction strategy for a cache of size k . We demonstrate that naively following the oracle’s recommendations may lead to very poor performance, even when the average error is quite low. Instead, we show how to modify the Marker algorithm to take into account the predictions and prove that this combined approach achieves a competitive ratio that both (i) decreases as the predictor’s error decreases and (ii) is always capped by O (log k ), which can be achieved without any assistance from the predictor. We complement our results with an empirical evaluation of our algorithm on real-world datasets and show that it performs well empirically even when using simple off-the-shelf predictions.

APA, Harvard, Vancouver, ISO, and other styles

25

Ma, Weimin, and Xiaodong Ji. "Online Work-Break Problem and its Competitive Analysis." Asia-Pacific Journal of Operational Research 33, no. 02 (April 2016): 1650011. http://dx.doi.org/10.1142/s0217595916500111.

Full text

Abstract:

An original online problem with decreasing profit growth rate is proposed to optimize the work hours of employees, named the online work-break problem (WBP). In this problem, the manager has to answer for an abstract worker when he should have a break for his work efficiency declines with the durative time of work period. The efficiency of the worker is presented by a work efficiency function [Formula: see text] in the description of our problem. We present the online algorithms to solve the WBP based on linear estimation of [Formula: see text] under two levels. Both the problems with single-period and dynamic multi-periods have 2-competitive online algorithms.

APA, Harvard, Vancouver, ISO, and other styles

26

Burjons, Elisabet, Juraj Hromkovič, Rastislav Královič, Richard Královič, Xavier Muñoz, and Walter Unger. "Online Graph Coloring Against a Randomized Adversary." International Journal of Foundations of Computer Science 29, no. 04 (June 2018): 551–69. http://dx.doi.org/10.1142/s0129054118410058.

Full text

Abstract:

We consider an online model where an adversary constructs a set of [Formula: see text] instances [Formula: see text] instead of one single instance. The algorithm knows [Formula: see text] and the adversary will choose one instance from [Formula: see text] at random to present to the algorithm. We further focus on adversaries that construct sets of [Formula: see text]-chromatic instances. In this setting, we provide upper and lower bounds on the competitive ratio for the online graph coloring problem as a function of the parameters in this model. Both bounds are linear in [Formula: see text] and matching upper and lower bound are given for a specific set of algorithms that we call “minimalistic online algorithms”.

APA, Harvard, Vancouver, ISO, and other styles

27

Hoeller, Frank. "LEO: Liquid Exploration Online." International Journal of Robotic Computing 2, no. 1 (April 1, 2020): 58–80. http://dx.doi.org/10.35708/rc1869-126259.

Full text

Abstract:

This article introduces a novel approach to the online complete- coverage path planning (CCPP) problem that is specically tailored to the needs of skid-steer tracked robots. In contrast to most of the current state-of-the-art algorithms for this task, the proposed algorithm reduces the number of turning maneuvers, which are responsible for a large part of the robot's energy consumption. Nevertheless, the approach still keeps the total distance traveled at a competitive level. The algorithm operates on a grid-based environment representation and uses a 3x3 prioritization matrix for local navigation decisions. This matrix prioritizes cardinal di- rections leading to a preference for straight motions. In case no progress can be achieved based on a local decision, global path planning is used to choose a path to the closest known unvisited cell, thereby guaranteeing completeness of the approach. In an extensive evaluation using simulation experiments, we show that the new algorithm indeed generates competi- tively short paths with largely reduced turning costs, compared to other state-of-the-art CCPP algorithms. We also illustrate its performance on a real robot.

APA, Harvard, Vancouver, ISO, and other styles

28

Chai, Xing, Lingfa Lu, Wenhua Li, and Liqi Zhang. "Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time." Asia-Pacific Journal of Operational Research 35, no. 06 (December 2018): 1850048. http://dx.doi.org/10.1142/s0217595918500483.

Full text

Abstract:

In this paper, we consider the online single machine scheduling problem to minimize the maximum weighted completion time of the jobs. For the preemptive problem, we show that the LW (Largest Weight first) rule yields an optimal schedule. For the non-preemptive problem, Li [Li, W (2015). A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time. Asia-Pacific Journal of Operational Research, 32(4), 1550030 (10 pages)] presented a lower bound 2, and then provided an online algorithm with a competitive ratio of 3. In this paper, we present two online algorithms with the best-possible competitive ratio of [Formula: see text] for the non-preemptive problem.

APA, Harvard, Vancouver, ISO, and other styles

29

van Stee, Rob. "SIGACT News Online Algorithms Column 37." ACM SIGACT News 52, no. 2 (June 14, 2021): 71. http://dx.doi.org/10.1145/3471469.3471480.

Full text

Abstract:

For this issue, Pavel Vesely has contributed a wonderful overview of the ideas that were used in his SODA paper on packet scheduling with Marek Chrobak, Lukasz Jez and Jiri Sgall. This is a problem for which a 2-competitive algorithm as well as a lower bound of ϕ ≈ 1:618 was known already twenty years ago, but which resisted resolution for a long time. It is great that this problem has nally been resolved and that Pavel was willing to explain more of the ideas behind it for this column. He also provides an overview of open problems in this area.

APA, Harvard, Vancouver, ISO, and other styles

30

Fotakis, Dimitris, Loukas Kavouras, and Lydia Zakynthinou. "Online Facility Location in Evolving Metrics." Algorithms 14, no. 3 (February 25, 2021): 73. http://dx.doi.org/10.3390/a14030073.

Full text

Abstract:

The Dynamic Facility Location problem is a generalization of the classic Facility Location problem, in which the distance metric between clients and facilities changes over time. Such metrics that develop as a function of time are usually called “evolving metrics”, thus Dynamic Facility Location can be alternatively interpreted as a Facility Location problem in evolving metrics. The objective in this time-dependent variant is to balance the trade-off between optimizing the classic objective function and the stability of the solution, which is modeled by charging a switching cost when a client’s assignment changes from one facility to another. In this paper, we study the online variant of Dynamic Facility Location. We present a randomized O(logm+logn)-competitive algorithm, where m is the number of facilities and n is the number of clients. In the first step, our algorithm produces a fractional solution, in each timestep, to the objective of Dynamic Facility Location involving a regularization function. This step is an adaptation of the generic algorithm proposed by Buchbinder et al. in their work “Competitive Analysis via Regularization.” Then, our algorithm rounds the fractional solution of this timestep to an integral one with the use of exponential clocks. We complement our result by proving a lower bound of Ω(m) for deterministic algorithms and lower bound of Ω(logm) for randomized algorithms. To the best of our knowledge, these are the first results for the online variant of the Dynamic Facility Location problem.

APA, Harvard, Vancouver, ISO, and other styles

31

Albers, Susanne, Arindam Khan, and Leon Ladewig. "Improved Online Algorithms for Knapsack and GAP in the Random Order Model." Algorithmica 83, no. 6 (February 17, 2021): 1750–85. http://dx.doi.org/10.1007/s00453-021-00801-2.

Full text

Abstract:

AbstractThe knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939–1964, 2018). Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939–1964, 2018).

APA, Harvard, Vancouver, ISO, and other styles

32

Ma, Hang. "Extended Abstract: A Competitive Analysis of Online Multi-Agent Path Finding." Proceedings of the International Symposium on Combinatorial Search 12, no. 1 (July 21, 2021): 182–84. http://dx.doi.org/10.1609/socs.v12i1.18577.

Full text

Abstract:

This is an extended abstract of a paper to be published at ICAPS 2021. We study online Multi-Agent Path Finding (MAPF), where new agents are constantly revealed over time and all agents must find collision-free paths to their given goal locations. We generalize existing complexity results of (offline) MAPF to online MAPF. We classify online MAPF algorithms into different categories. We present several complexity and competitiveness results for online MAPF and its algorithms, which provides theoretical insights into the effectiveness of using MAPF algorithms in an online setting for the first time.

APA, Harvard, Vancouver, ISO, and other styles

33

Qin, Tiancheng, and S. Rasoul Etesami. "Optimal Online Algorithms for File-Bundle Caching and Generalization to Distributed Caching." ACM Transactions on Modeling and Performance Evaluation of Computing Systems 6, no. 1 (June 2021): 1–23. http://dx.doi.org/10.1145/3445028.

Full text

Abstract:

We consider a generalization of the standard cache problem called file-bundle caching, where different queries (tasks), each containing l ≥ 1 files, sequentially arrive. An online algorithm that does not know the sequence of queries ahead of time must adaptively decide on what files to keep in the cache to incur the minimum number of cache misses. Here a cache miss refers to the case where at least one file in a query is missing among the cache files. In the special case where l = 1, this problem reduces to the standard cache problem. We first analyze the performance of the classic least recently used (LRU) algorithm in this setting and show that LRU is a near-optimal online deterministic algorithm for file-bundle caching with regard to competitive ratio. We then extend our results to a generalized ( h,k )-paging problem in this file-bundle setting, where the performance of the online algorithm with a cache size k is compared to an optimal offline benchmark of a smaller cache size h < k . In this latter case, we provide a randomized O ( l ln k / k-h )-competitive algorithm for our generalized ( h, k )-paging problem, which can be viewed as an extension of the classic marking algorithm . We complete this result by providing a matching lower bound for the competitive ratio, indicating that the performance of this modified marking algorithm is within a factor of 2 of any randomized online algorithm. Finally, we look at the distributed version of the file-bundle caching problem where there are m ≥ 1 identical caches in the system. In this case, we show that for m = l + 1 caches, there is a deterministic distributed caching algorithm that is ( l 2 + l )-competitive and a randomized distributed caching algorithm that is O ( l ln ( 2l + 1)-competitive when l ≥ 2. We also provide a general framework to devise other efficient algorithms for the distributed file-bundle caching problem and evaluate the performance of our results through simulations.

APA, Harvard, Vancouver, ISO, and other styles

34

Zeynali, Ali, Bo Sun, Mohammad Hajiesmaili, and Adam Wierman. "Data-driven Competitive Algorithms for Online Knapsack and Set Cover." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 12 (May 18, 2021): 10833–41. http://dx.doi.org/10.1609/aaai.v35i12.17294.

Full text

Abstract:

The design of online algorithms has tended to focus on algorithms with worst-case guarantees, e.g., bounds on the competitive ratio. However, it is well-known that such algorithms are often overly pessimistic, performing sub-optimally on non-worst-case inputs. In this paper, we develop an approach for data-driven design of online algorithms that maintain near-optimal worst-case guarantees while also performing learning in order to perform well for typical inputs. Our approach is to identify policy classes that admit global worst-case guarantees, and then perform learning using historical data within the policy classes. We demonstrate the approach in the context of two classical problems, online knapsack and online set cover, proving competitive bounds for rich policy classes in each case. Additionally, we illustrate the practical implications via a case study on electric vehicle charging.

APA, Harvard, Vancouver, ISO, and other styles

35

Khadiev, Kamil, and Aliya Khadieva. "Quantum and Classical Log-Bounded Automata for the Online Disjointness Problem." Mathematics 10, no. 1 (January 4, 2022): 143. http://dx.doi.org/10.3390/math10010143.

Full text

Abstract:

We consider online algorithms with respect to the competitive ratio. In this paper, we explore one-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. For a specially constructed online minimization problem, we provide a quantum log-bounded automaton that is more effective (has less competitive ratio) than classical automata, even with advice, in the case of the logarithmic size of memory. We construct an online version of the well-known Disjointness problem as a problem. It was investigated by many researchers from a communication complexity and query complexity point of view.

APA, Harvard, Vancouver, ISO, and other styles

36

Januszewski, Janusz, and Łukasz Zielonka. "Improved Online Algorithms for 2-Space Bounded 2-Dimensional Bin Packing." International Journal of Foundations of Computer Science 27, no. 04 (June 2016): 407–29. http://dx.doi.org/10.1142/s0129054116500076.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Zhao, Tianming, Wei Li, and Albert Y. Zomaya. "Uniform Machine Scheduling with Predictions." Proceedings of the International Conference on Automated Planning and Scheduling 32 (June 13, 2022): 413–22. http://dx.doi.org/10.1609/icaps.v32i1.19827.

Full text

Abstract:

The revival in learning theory has provided us with improved capabilities for accurate predictions. This work contributes to an emerging research agenda of online scheduling with predictions by studying the makespan minimization in uniformly related machine non-clairvoyant scheduling with job size predictions. Our task is to design online algorithms that effectively use predictions and have performance guarantees with varying prediction quality. We first propose a simple algorithm-independent prediction error measurement to quantify prediction quality. To effectively use the predicted job sizes, we design an offline improved 2-relaxed decision procedure approximating the optimal schedule. With this decision procedure, we propose an online O(min{log eta, log m})-competitive algorithm that assumes a known prediction error. Finally, we extend this algorithm to construct a robust O(min{log eta, log m})-competitive algorithm that does not assume a known error. Both algorithms require only moderate predictions to improve the well-known Omega(log m) lower bound, showing the potential of using predictions in managing uncertainty.

APA, Harvard, Vancouver, ISO, and other styles

38

Assadi, Sepehr, Justin Hsu, and Shahin Jabbari. "Online Assignment of Heterogeneous Tasks in Crowdsourcing Markets." Proceedings of the AAAI Conference on Human Computation and Crowdsourcing 3 (September 23, 2015): 12–21. http://dx.doi.org/10.1609/hcomp.v3i1.13236.

Full text

Abstract:

We investigate the problem of heterogeneous task assignment in crowdsourcing markets from the point of view of the requester, who has a collection of tasks. Workers arrive online one by one, and each declare a set of feasible tasks they can solve, and desired payment for each feasible task. The requester must decide on the fly which task (if any) to assign to the worker, while assigning workers only to feasible tasks. The goal is to maximize the number of assigned tasks with a fixed overall budget. We provide an online algorithm for this problem and prove an upper bound on the competitive ratio of this algorithm against an arbitrary (possibly worst-case) sequence of workers who want small payments relative to the requester’s total budget. We further show an almost matching lower bound on the competitive ratio of any algorithm in this setting. Finally, we propose a different algorithm that achieves an improved competitive ratio in the random permutation model, where the order of arrival of the workers is chosen uniformly at random. Apart from these strong theoretical guarantees, we carry out experiments on simulated data which demonstrates the practical applicability of our algorithms.

APA, Harvard, Vancouver, ISO, and other styles

39

Chin, Francis Y. L., and Stanley P. Y. Fung. "Improved competitive algorithms for online scheduling with partial job values." Theoretical Computer Science 325, no. 3 (October 2004): 467–78. http://dx.doi.org/10.1016/j.tcs.2004.02.046.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Chin, Francis Y. L., Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Jiří Sgall, and Tomáš Tichý. "Online competitive algorithms for maximizing weighted throughput of unit jobs." Journal of Discrete Algorithms 4, no. 2 (June 2006): 255–76. http://dx.doi.org/10.1016/j.jda.2005.03.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Sun, Bo, Ali Zeynali, Tongxin Li, Mohammad Hajiesmaili, Adam Wierman, and Danny H. K. Tsang. "Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging." ACM SIGMETRICS Performance Evaluation Review 49, no. 1 (June 22, 2022): 67–68. http://dx.doi.org/10.1145/3543516.3456271.

Full text

Abstract:

We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literatures. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, in the full version of this paper, we illustrate the proposed algorithm via trace-based experiments of EV charging.

APA, Harvard, Vancouver, ISO, and other styles

42

Chen, Weirong, Jiaqi Zheng, Haoyu Yu, Guihai Chen, Yixin Chen, and Dongsheng Li. "Online Learning Bipartite Matching with Non-stationary Distributions." ACM Transactions on Knowledge Discovery from Data 16, no. 5 (October 31, 2022): 1–22. http://dx.doi.org/10.1145/3502734.

Full text

Abstract:

Online bipartite matching has attracted wide interest since it can successfully model the popular online car-hailing problem and sharing economy. Existing works consider this problem under either adversary setting or i.i.d. setting. The former is too pessimistic to improve the performance in the general case; the latter is too optimistic to deal with the varying distribution of vertices. In this article, we initiate the study of the non-stationary online bipartite matching problem, which allows the distribution of vertices to vary with time and is more practical. We divide the non-stationary online bipartite matching problem into two subproblems, the matching problem and the selecting problem, and solve them individually. Combining Batch algorithms and deep Q-learning networks, we first construct a candidate algorithm set to solve the matching problem. For the selecting problem, we use a classical online learning algorithm, Exp3, as a selector algorithm and derive a theoretical bound. We further propose CDUCB as a selector algorithm by integrating distribution change detection into UCB. Rigorous theoretical analysis demonstrates that the performance of our proposed algorithms is no worse than that of any candidate algorithms in terms of competitive ratio. Finally, extensive experiments show that our proposed algorithms have much higher performance for the non-stationary online bipartite matching problem comparing to the state-of-the-art.

APA, Harvard, Vancouver, ISO, and other styles

43

Gao, Qiang, Ganggang Li, and Xiwen Lu. "Online and semi-online scheduling to minimize makespan on single machine with an availability constraint." Discrete Mathematics, Algorithms and Applications 07, no. 03 (September 2015): 1550021. http://dx.doi.org/10.1142/s1793830915500214.

Full text

Abstract:

Online and semi-online scheduling problems on a single machine with an availability constraint are considered in this paper. The machine has one unavailable interval in which jobs cannot be processed. Preemption is not allowed. Jobs arrive over time. The objective is to minimize makespan. First we discuss the online version of the problem. After giving its lower bound, we prove that Earliest Release Date (ERD) algorithm is an optimal algorithm. Then we study some semi-online problems in which the largest processing time, the total processing time, the largest release date, or the optimal makespan is known in advance. For these semi-online problems, we give their lower bounds, design semi-online algorithms and prove their competitive ratios, respectively.

APA, Harvard, Vancouver, ISO, and other styles

44

Jarsulic, Marc. "Addressing the Competitive Harms of Opaque Online Surveillance and Recommendation Algorithms." Antitrust Bulletin 67, no. 1 (January 19, 2022): 100–112. http://dx.doi.org/10.1177/0003603x211066983.

Full text

Abstract:

Facebook and Alphabet operate free internet services that are widely used. They provide these services for free because users are online ad targets. Together Facebook and Alphabet have a large share of the market for online advertising in the U.S. Their dominance delivers monopolistic returns, reflected in the persistently high valuations financial markets place on each company. Online ad sales depend on the ability of these platforms to individually target ads and messages to huge numbers of people. Targeting is made possible by surveillance which is large in scale, scope, and effectiveness. User engagement, which helps determine target numbers, is stimulated and directed by “recommendation” algorithms on Facebook and Alphabet’s YouTube platform. These algorithms can affect what users read and view, and can influence their attitudes, emotions, and behavior. While surveillance has negative effects on user privacy, and algorithms have had powerful effects on user attitudes and behavior, platform users have limited knowledge about how these practices operate or their impacts. These information asymmetries between platforms and users have important competitive effects. They divert users from competing platforms that do not engage in these business practices, and inhibit entry and the innovation it would stimulate, thereby helping sustain the monopoly power of dominant incumbents. Section 5 of the Federal Trade Commission Act, which prohibits “unfair methods of competition” and includes rulemaking authority, may be the most effective way to address anticompetitive practices that are technically complex, can evolve rapidly, and are difficult for industry outsiders to observe.

APA, Harvard, Vancouver, ISO, and other styles

45

JIANG, YIWEI, AN ZHANG, and JUELIANG HU. "OPTIMAL ONLINE ALGORITHMS ON TWO HIERARCHICAL MACHINES WITH RESOURCE AUGMENTATION." Discrete Mathematics, Algorithms and Applications 04, no. 01 (March 2012): 1250012. http://dx.doi.org/10.1142/s1793830912500127.

Full text

Abstract:

This paper investigates an online hierarchical scheduling problem with resource augmentation, i.e., the resources of the online algorithms are different from those of the offline algorithms. The machines are provided with different capacity according to their hierarchies. One with the hierarchy 1 has a speed of s(q) in the online (offline) algorithms and can process all the jobs. The other with hierarchy 2 has a speed of 1 in the online/offline algorithms and can only process partial jobs. The objective is to minimize makespan. For any 0 < q, s < ∞, we present optimal online algorithms with parametric competitive ratios.

APA, Harvard, Vancouver, ISO, and other styles

46

Sun, Bo, Lin Yang, Mohammad Hajiesmaili, Adam Wierman, John C. S. Lui, Don Towsley, and Danny H. K. Tsang. "The Online Knapsack Problem with Departures." Proceedings of the ACM on Measurement and Analysis of Computing Systems 6, no. 3 (December 2022): 1–32. http://dx.doi.org/10.1145/3570618.

Full text

Abstract:

The online knapsack problem is a classic online resource allocation problem in networking and operations research. Its basic version studies how to pack online arriving items of different sizes and values into a capacity-limited knapsack. In this paper, we study a general version that includes item departures, while also considering multiple knapsacks and multi-dimensional item sizes. We design a threshold-based online algorithm and prove that the algorithm can achieve order-optimal competitive ratios. Beyond worst-case performance guarantees, we also aim to achieve near-optimal average performance under typical instances. Towards this goal, we propose a data-driven online algorithm that learns within a policy-class that guarantees a worst-case performance bound. In trace-driven experiments, we show that our data-driven algorithm outperforms other benchmark algorithms in an application of online knapsack to job scheduling for cloud computing.

APA, Harvard, Vancouver, ISO, and other styles

47

Buchbinder, Niv, and Joseph (Seffi) Naor. "The Design of Competitive Online Algorithms via a Primal—Dual Approach." Foundations and Trends® in Theoretical Computer Science 3, no. 2–3 (2009): 93–263. http://dx.doi.org/10.1561/0400000024.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Buchbinder, Niv, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, and Maxim Sviridenko. "Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms." Operations Research 61, no. 4 (August 2013): 1014–29. http://dx.doi.org/10.1287/opre.2013.1188.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Eghbali, Reza, James Saunderson, and Maryam Fazel. "Competitive online algorithms for resource allocation over the positive semidefinite cone." Mathematical Programming 170, no. 1 (June 12, 2018): 267–92. http://dx.doi.org/10.1007/s10107-018-1305-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Bachrach, El-Yaniv, and Reinstädtler. "On the Competitive Theory and Practice of Online List Accessing Algorithms." Algorithmica 32, no. 2 (February 2002): 201–45. http://dx.doi.org/10.1007/s00453-001-0069-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Competitive online algorithms'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles