Search

This paper studies the multiple period inventory replenishment problem for a capacitated warehouse when procurement prices and market demands are both uncertain, with the goal to minimise the procuring and holding costs. We analyse this problem under the framework of competitive analysis, where neither probabilistic distributions nor sets are available to characterise the unknown price and demand parameters. An efficient online real-time replenishment algorithm is developed, which is free of any distribution assumption, and the decisions are made based entirely on past and present information. We derive an instance-independent competitive ratio of the algorithm, which provides a worst-case theoretical performance guarantee, and shows that the proposed algorithm performs well for situations with high volatility uncertainty over time and is naturally risk-averse. Finally, a set of numerical experiments further verifies the effectiveness of the algorithm. [ABSTRACT FROM AUTHOR]

This paper addresses the semi-online scheduling problem of minimising the total weighted completion time on a single machine, where a combination of information on jobs release dates and processing times is considered. In this study, jobs can only arrive at known future times and a lower bound on jobs processing times is known in advance. A new semi-online algorithm is presented and is shown to be the best possible for the considered problem. In order to make this statement, a new lower bound on the competitive ratio of any semi-online algorithm for the problem is developed and, using competitive analysis, the proposed semi-online algorithm is shown to have a competitive ratio that matches the lower bound. [ABSTRACT FROM AUTHOR]

AbstractThis article introduces the traveling salesman problem with a truck and a drone under incomplete information (TSP-DI). TSP-DI is motivated by the deliveries of emergency supplies under unknown road conditions in the immediate aftermath of a disastrous event. The urgency may force the immediate dispatch of relief vehicles, such that road damages blocking the truck’s planned route are detected “on-the-fly”. The relief transport must schedule deliveries anticipating possible unplanned truck detours, enforce (planned) drone detours for early checking of key road segments, and consider the dynamic nature of road condition information. In this investigation, we perform a competitive analysis of a widely used delivery policy for TSP-DI in practice – the online re-optimization policy (Reopt) – and compare it with several alternative delivery strategies. Competitive analysis examines the worst-case performance of the strategies and is particularly important in the context of disaster relief, where worst-case outcomes must be avoided. Our analysis shows that Reopt is dominated by alternative delivery policies in terms of the competitive ratio even at a medium level of damage on the road. It also underscores the importance of surveillance detours performed by the drone, even if the surveillance delays the start of the deliveries. [ABSTRACT FROM AUTHOR]

Competitor identification (CI) is an essential step in establishing an effective competitive business strategy. For complex business environments, network-based CI methods have been studied in the literature, aiming to shed light on the blind spots in managers' radars. Typically, CI is based on networks without temporal information, despite the dynamic changes in business environments. Alternatively, the temporal information is considered in CI by simply accumulating the intensities of synchronous interfirm competition evaluated over time. As a result, competitors' actions in the past are overlooked in evaluations of interfirm competition, although such actions remain in managers' memories. In this study, we propose a new method for CI incorporating memories of the past transactions of competitors in a dynamic network. The proposed method measures the interfirm competition between firms based on their resource similarity and market commonality in a dynamic financial transaction network. The proposed method facilitates capturing the asynchronous competition from suppliers and demanders taken by competitors. We evaluate the proposed method on a toy network and on a case of interfirm transactions in Korea from 2011 to 2014. The results show that the temporal information in dynamic networks and memory about past transactions improves the predictive accuracy in CI with the proposed method. [ABSTRACT FROM AUTHOR]

Data-structure dynamization is a general approach for making static data structures dynamic. It is used extensively in geometric settings and in the guise of so-called merge (or compaction) policies in big-data databases such as LevelDB and Google Bigtable. Previous theoretical work is based on worst-case analyses for uniform inputs—insertions of one item at a time and non-varying read rate. In practice, merge policies must not only handle batch insertions and varying read/write ratios, they can take advantage of such non-uniformity to reduce cost on a per-input basis. To model this, we initiate the study of data-structure dynamization through the lens of competitive analysis via two new online set-cover problems. For each, the input is a sequence of disjoint sets of weighted items. The sets are revealed one at a time. The algorithm must respond to each with a set cover that covers all items revealed so far. It obtains the cover incrementally from the previous cover by adding one or more sets and optionally removing existing sets. For each new set the algorithm incurs build cost equal to the weight of the items in the set. In the first problem the objective is to minimize total build cost plus total query cost, where the algorithm incurs a query cost at each time \(t\) equal to the current cover size. In the second problem, the objective is to minimize the build cost while keeping the query cost from exceeding \(k\) (a given parameter) at any time. We give deterministic online algorithms for both variants, with competitive ratios of \(\Theta(\log^{*}n)\) and \(k\) , respectively. The latter ratio is optimal for the second variant. [ABSTRACT FROM AUTHOR]

Renting servers in the cloud is a generalization of the bin packing problem, motivated by job allocation to servers in cloud computing applications. Jobs arrive in an online manner, and need to be assigned to servers; their duration and size are known at the time of arrival. There is an infinite supply of identical servers, each having one unit of computational capacity per unit of time. A server can be rented at any time and continues to be rented until all jobs assigned to it finish. The cost of an assignment is the sum of durations of rental periods of all servers. The goal is to assign jobs to servers to minimize the overall cost while satisfying server capacity constraints. We focus on analyzing two natural algorithms, NextFit and FirstFit , for the case of jobs of equal duration. It is known that the competitive ratio of NextFit and FirstFit are at most 3 and 4 respectively for this case. We prove a tight bound of 2 on the competitive ratio of NextFit. For FirstFit , we establish a lower bound of ≈ 2. 519 on the competitive ratio, even when jobs have only two distinct arrival times 0 and t. Using the weight function technique, we show that this bound is almost tight when there are only two arrival times; we obtain an upper bound of 2.565 on the asymptotic competitive ratio of FirstFit. In fact, we show an upper bound of 168 131 (1 + t) on the asymptotic competitive ratio for any t > 0. 559. For the case when jobs have arrival times 0 and 1 and duration 2, we show a lower bound of ≈ 1. 89 and an upper bound of 2 on the strict competitive ratio of FirstFit. Finally, we show an upper bound of 3 / 2 on the competitive ratio of long-running uniform servers. [ABSTRACT FROM AUTHOR]

A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. The prediction available to the online algorithm is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio r = a a ^ where a is the actual value for this average size and a ^ is the prediction. We give an algorithm which is e - 1 e -competitive, if r = 1 , and this is best possible among online algorithms knowing a and nothing else. More generally, the algorithm has a competitive ratio of e - 1 e r , if r ≤ 1 , and e - r e r , if 1 ≤ r < e . Any algorithm with a better competitive ratio for some r < 1 will have a worse competitive ratio for some r > 1 . To obtain a positive competitive ratio for all r, we adjust the algorithm, resulting in a competitive ratio of 1 2 r for r ≥ 1 and r 2 for r ≤ 1 . We show that improving the result for any r < 1 leads to a worse result for some r > 1 . [ABSTRACT FROM AUTHOR]

Purpose: Search Engine Optimisation (SEO) covers processes aimed at improving website quality. SEO audits can be used to conduct comparative and competitive analyses to identify good practices employed by other online platforms. The article scores selected marketplace and e-commerce websites in terms of search engine optimisation. Design/methodology/approach: We analyse the quality of selected marketplace and e-commerce websites with synthetic aggregate metrics, so-called SEO Score. The first stage involved exploratory quality tests, whereby the home page source code was analysed for every website. The second stage was algorithmic tests using selected online tools. Findings: The websites scored 2,126 out of 3,000 points in total. It is 71% of the maximum score. This means that, according to the test applications, not many attributes require SEO effort under the employed research design. Four out of the five tested websites had their names (brands) in the meta description tag. All the portals had the title tag. However, only one site had the meta keywords tag. Originality/value: The research apparatus employed is sufficient to identify basic design flaws, which makes it useful for competitive analysis. Our algorithmic analysis pinpointed differences in the quality of leading marketplace and e-commerce websites in Poland. The exploratory research revealed certain good practices regarding meta information on marketplace and e-commerce websites, which may affect SEO. [ABSTRACT FROM AUTHOR]

The online graph exploration problem, which was proposed by Kalyanasundaram and Pruhs (Theor Comput Sci 130(1):125–138, 1994), is defined as follows: Given an edge-weighted undirected connected graph and a specified vertex (called the origin), the task of an algorithm is to compute a path from the origin to the origin which contains all the vertices of the given graph. The goal of the problem is to find such a path of minimum weight. At each time, an online algorithm knows only the weights of edges each of which consists of visited vertices or vertices adjacent to visited vertices. Fritsch (Inform Process Lett 168:1006096, 2021) showed that the competitive ratio of an online algorithm is at most three for any unicyclic graph. On the other hand, Brandt et al. (Theor Comput Sci 839:176–185, 2020) showed a lower bound of two on the competitive ratio for any unicyclic graph. In this paper, we showed the competitive ratio of an online algorithm is at most 5/2 for any unicyclic graph. [ABSTRACT FROM AUTHOR]

This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on m identical machines. The main result is an O(1) competitive deterministic algorithm for any number of machines m > 1 . [ABSTRACT FROM AUTHOR]

In the online facility assignment problem OFA (k , { c i } i = 1 k) , there exist k servers s 1 , ... , s k on a metric space where each s i has an integer capacity c i and a request arrives one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. As special cases for OFA (k , { c i } i = 1 k) , we consider OFA (k , { c i } i = 1 k) on a line , which is denoted by OFAL (k , { c i } i = 1 k) and OFAL eq (k , { c i } i = 1 k) , where the latter is the case of OFAL (k , { c i } i = 1 k) with equidistant servers. In this paper, we perform the competitive analysis for the above problems. As a natural generalization of the greedy algorithm grdy, we introduce a class of algorithms called MPFS (Most Preferred Free Servers) and show that any MPFS algorithm has the capacity-insensitive property, i.e., for any MPFS algorithm alg for OFA (k , { c i } i = 1 k) , if alg is c -competitive when c 1 = ⋯ = c k = 1 , then alg is c -competitive for general { c i } i = 1 k . By applying the capacity-insensitive property of the greedy algorithm grdy, we derive the matching upper and lower bounds 4 k − 5 on the competitive ratio of grdy for OFAL eq (k , { c i } i = 1 k). To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm alg for OFAL eq (k , { c i } i = 1 k) is at least 2 k − 1. Then, we propose a new MPFS algorithm idas (Interior Division for Adjacent Servers) for OFAL (k , { c i } i = 1 k) and show that the competitive ratio of idas for OFAL eq (k , { c i } i = 1 k) is at most 2 k − 1 , i.e., idas for OFAL eq (k , { c i } i = 1 k) is best possible in all the MPFS algorithms. We also give numerical experiments to investigate the performance of idas and grdy and show that idas performs better than grdy for distribution of request sequences with locality. [ABSTRACT FROM AUTHOR]

Consider a collection of entities moving continuously with bounded speed, but otherwise unpredictably, in some low-dimensional space. Two such entities encroach upon one another at a fixed time if their separation is less than some specified threshold. Encroachment, of concern in many settings such as collision avoidance, may be unavoidable. However, the associated difficulties are compounded if there is uncertainty about the precise location of entities, giving rise to potential encroachment and, more generally, potential congestion within the full collection. We adopt a model in which entities can be queried for their current location (at some cost) and the uncertainty region associated with an entity grows in proportion to the time since that entity was last queried. The goal is to maintain low potential congestion, measured in terms of the (dynamic) intersection graph of uncertainty regions, at specified (possibly all) times, using the lowest possible query cost. Previous work in the same uncertainty model addressed the problem of minimizing the congestion potential of point entities using location queries of some bounded frequency. It was shown that it is possible to design query schemes that are O (1) -competitive, in terms of worst-case congestion potential, with other, even clairvoyant query schemes (that exploit knowledge of the trajectories of all entities), subject to the same bound on query frequency. In this paper, we initiate the treatment of a more general problem with the complementary optimization objective: minimizing the query frequency, measured as the reciprocal of the minimum time between queries (granularity), while guaranteeing a fixed bound on congestion potential of entities with positive extent at one specified target time. This complementary objective necessitates quite different schemes and analyses. Nevertheless, our results parallel those of the earlier papers, specifically tight competitive bounds on required query frequency. [ABSTRACT FROM AUTHOR]

We study an online distribution problem in which a producer has to send a load from an origin to a destination. At each time period before the deadline, they ask for transportation price quotes and have to decide to either accept or not accept the minimum offered price. If this price is not accepted, they have to pay a penalty cost, which may be the cost to ask for new quotes, the penalty cost for a late delivery, or the inventory cost to store the load for a certain duration. The aim is to minimize the sum of the transportation and the penalty costs. This problem has interesting real-world applications, given that transportation quotes can be obtained from professional websites nowadays. We show that the classical online algorithm used to solve the well-known Secretary problem is not able to provide, on average, effective solutions to our problem, given the trade-off between the transportation and the penalty costs. Therefore, we design two classes of online algorithms. The first class is based on a given time of acceptance, while the second is based on a given threshold price. We formally prove the competitive ratio of each algorithm, i.e., the worst-case performance of the online algorithm with respect to the optimal solution of the offline problem, in which all transportation prices are known at the beginning, rather than being revealed over time. The computational results show the algorithms' performance on average and in the worst-case scenario when the transportation prices are generated on the basis of given probability distributions. [ABSTRACT FROM AUTHOR]

This article studies the Minimum Spanning Tree Problem under Explorable Uncertainty as well as a related vertex uncertainty version of the problem. We particularly consider special instance types, including cactus graphs, for which we provide randomized algorithms. We introduce the problem of finding a minimum weight spanning star under uncertainty for which we show that no algorithm can achieve constant competitive ratio. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of online car-sharing with variable booking times (CSV for short). In this scenario, customers submit ride requests, each specifying two important time parameters: the booking time and the pick-up time (start time), as well as two location parameters—the pick-up location and the drop-off location within a graph. For each request, it’s important to note that it must be booked before its scheduled start time. The booking time can fall within a specific interval prior to the request’s starting time. Additionally, each car is capable of serving only one request at any given time. The primary objective of the scheduler is to optimize the utilization of k cars to serve as many requests as possible. As requests arrive at their booking times, the scheduler faces an immediate decision: whether to accept or decline the request. This decision must be made promptly upon request submission, precisely at the booking time. We prove that no deterministic online algorithm can achieve a competitive ratio smaller than L + 1 even on a special case of a path (where L denotes the ratio between the largest and the smallest request travel time). For general graphs, we give a Greedy Algorithm that achieves (3 L + 1) -competitive ratio for CSV. We also give a Parted Greedy Algorithm with competitive ratio (5 2 L + 10) when the number of cars k is no less than 5 4 L + 20 ; for CSV on a special case of a path, the competitive ratio of Parted Greedy Algorithm is (2 L + 10) when k ≥ L + 20 . [ABSTRACT FROM AUTHOR]

Online algorithms are crucial for real-time decision-making and adaptability across diverse fields, such as operations research, computer science, and combinatorics. These algorithms handle data incrementally and make decisions without prior knowledge of future inputs, thereby effectively addressing complex challenges. This study provides a comprehensive survey of online algorithms, focusing on the Set Cover problem (SC). SC is one of the most extensively studied NP-complete problems, contributing significantly to advancements in approximation techniques, complexity theory, and online algorithms research. It involves selecting a minimal-weight subset from a collection of subsets to cover all elements. This survey examines online algorithms for Set Cover in multiple contexts, including competitive analysis, stochastic models, advice complexity, predictive algorithms, and recourse strategies. While competitive analysis, which compares online algorithms to the best possible offline solutions, remains a key evaluation method, this paper aims to extend the understanding beyond traditional worst-case scenarios. By providing in-depth insights into algorithm design, analytical methods, and practical applications, it seeks to advance the field and stimulate further research in evolving contexts. Additionally, it underscores the intersection of online algorithms with broader domains such as machine learning and predictive analytics, establishing new benchmarks for exploring their broader implications.

Facility Location problems are one of the most prominent optimization problems in computer science, operations research, and combinatorial optimization. Their simple yet intrinsic structure has led to their widespread application in diverse fields, such as leasing, clustering, and urban planning. In facility location problems, potential sites for opening facilities, like warehouses, each have an associated opening cost. Client locations, such as stores, require service from a facility, incurring a cost proportional to their distance from them when assigned. Identifying optimal facility locations to minimize total costs associated with opening facilities and client assignment is the aim. This paper focuses on the online setting, in which client locations are revealed to the algorithm incrementally, unlike the classical offline setting, in which all client locations are given in advance. In this dynamic context, often referred to as the online algorithm scenario, immediate decisions are made to determine whether the newly disclosed client should be assigned to an existing facility or necessitate the establishment of a new facility. To gauge the effectiveness of online algorithms, the concept of competitive analysis is employed. This approach assesses the worst-case performance of online algorithms by comparing them to an optimal algorithm equipped with complete knowledge of forthcoming input sequences. Despite the considerable significance of the Facility Location problem and the substantial body of literature on it within the online algorithm framework, this article represents the first comprehensive summary of these research findings. It explores the algorithmic techniques employed, delves into practical applications, and identifies pertinent research gaps within this domain.

In the absence of any hazardous substances, colloidal gold nanoparticles (AuNPs) were synthesized through the reduction and stabilization of corresponding metal cations by a simple Eucommia ulmoides bark extract (EUBE). Employing these AuNPs as catalysts, at least ten distinct azo compounds were catalyzed and analyzed. The findings reveal outstanding catalytic performance across a diverse range of azo dyes, regardless of structural complexity, the count of azo bonds, the presence of various functional groups in the side chains, differences in molecular weight, degrees of water solubility, ionic characteristics of the dyes, and the particular class of dyes, whether reactive or acidic. Regardless of these varieties, azo dyes achieved over 90% degradation within 16 min, following a first-order pseudo-kinetic reaction. This report systematically explains the mechanics of AuNPs synthesis using EUBE and the step-by-step azo dye degradation. It signifies an advancement in azo-contaminated wastewater treatment, transcending the varied types and structural complexities of azo compounds.

We present a novel ${1}/{e}$ -competitive randomized $\epsilon $ -RANKING algorithm for the unweighted online trichromatic matching problem. This problem involves finding matching in tripartite graphs having three disjoint sets of vertices. Our model encompasses a tripartite graph configuration, where an offline vertex set is an intermediary connecting two opposite sets. The vertices from the latter sets arrive online individually over time. $\epsilon $ -RANKING employs a randomization strategy where offline vertices are assigned random ranks between [0, 1]. This approach exploits the principles of the $\bigg (1-\cfrac {1}{e}\bigg)$ -competitive randomized RANKING algorithm from the domain of online bipartite matching to the more complex context of online trichromatic matching. Furthermore, with numerical experiments, we demonstrate the effectiveness of our algorithm, both with real-world and synthetic data. This work addresses the challenges of online trichromatic matching and sets a benchmark for competitive algorithms within this domain.

Infrastructure-as-a-Service (IaaS) cloud platforms offer resources with diverse buying options. Users can run an instance on the on-demand market which is stable but expensive or on the spot market with a significant discount. However, users have to carefully weigh the low cost of spot instances against their poor availability. Spot instances will be revoked when the revocation event occurs. Thus, an important problem that an IaaS user faces now is how to use spot instances in a cost-effective and low-risk way. Based on the replication-based fault tolerance mechanism, we propose an online termination algorithm that optimizes the cost of using spot instances while ensuring operational stability. We prove that in most cases, the cost of our proposed online algorithm will not exceed twice the minimum cost of the optimal offline algorithm that knows the exact future a priori. Through a large number of experiments, we verify that our algorithm in most cases has a competitive ratio of no more than 2, and in other cases it can also reach the guaranteed competitive ratio. [ABSTRACT FROM AUTHOR]

Modern data centers suffer from immense power consumption. As a result, data center operators have heavily invested in capacity-scaling solutions, which dynamically deactivate servers if the demand is low and activate them again when the workload increases. We analyze a continuous-time model for capacity scaling, where the goal is to minimize the weighted sum of flow time, switching cost, and power consumption in an online fashion. We propose a novel algorithm, called adaptive balanced capacity scaling (ABCS), that has access to black-box machine learning predictions. ABCS aims to adapt to the predictions and is also robust against unpredictable surges in the workload. In particular, we prove that ABCS is (1+ε) competitive if the predictions are accurate, and yet, it has a uniformly bounded competitive ratio even if the predictions are completely inaccurate. Finally, we investigate the performance of this algorithm on a real-world data set and carry out extensive numerical experiments, which positively support the theoretical results. Funding: This work was partially supported by the Division of Computing and Communication Foundations [Grant 2113027]. The authors also acknowledge financial support for this project from the Algorithm and Randomness Center–Transdisciplinary Research Institute for Advancing Data Science Fellowship at Georgia Tech. [ABSTRACT FROM AUTHOR]

We consider the problem of maximizing a fractionally subadditive function under an increasing knapsack constraint. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most max\{ 3.293 M, 2M\}, under the assumption that the values of singleton sets are in the range [1,M], and we give a lower bound of max\{ 2.618,M\} on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a lower bound of max\{ 2,M\} and an upper bound of 2M for the incremental maximization of classical flows with capacities in [1,M] which is tight for the unit capacity case. [ABSTRACT FROM AUTHOR]

We introduce an online variant of mobile facility location (MFL) (introduced by Demaine et al. (SODA 258–267 2007)). We call this new problem online mobile facility location (OMFL). In the OMFL problem, initially, we are given a set of k mobile facilities with their starting locations. One by one, requests are added. After each request arrives, one can make some changes to the facility locations before the subsequent request arrives. Each request is always assigned to the nearest facility. The cost of this assignment is the distance from the request to the facility. The objective is to minimize the total cost, which consists of the relocation cost of facilities and the distance cost of requests to their nearest facilities. We provide a lower bound for the OMFL problem that even holds on uniform metrics. A natural approach to solve the OMFL problem for general metric spaces is to utilize hierarchically well-separated trees (HSTs) and directly solve the OMFL problem on HSTs. In this paper, we provide the first step in this direction by solving a generalized variant of the OMFL problem on uniform metrics that we call G-OMFL. We devise a simple deterministic online algorithm and provide a tight analysis for the algorithm. The second step remains an open question. Inspired by the k-server problem, we introduce a new variant of the OMFL problem that focuses solely on minimizing movement cost. We refer to this variant as M-OMFL. Additionally, we provide a lower bound for M-OMFL that is applicable even on uniform metrics. [ABSTRACT FROM AUTHOR]

Recently, online reviews have become a prevalent information source for competitive analysis because they provide rich information on the voices of customers. Based on online reviews, we propose a novel method named Integrated-Degree based K-shell decomposition (ID-KS) to conduct competitive analysis via product comparison networks. Under the consideration of feature differences among products, we apply text-mining approaches and ID-KS to convert online reviews into competitive insights including competitor identification, product comparison, product ranking, brand comparison and market-structure analysis. To validate the feasibility and the effectiveness of ID-KS, we demonstrate our approach in two cases, SUV cars and laptops, and compare it with state-of-the-art methods. The results show that ID-KS analyzes product comparison networks more effectively and properly, and it derives comprehensive comparative insights that are not fully captured by existing studies. [ABSTRACT FROM AUTHOR]

With a rapidly growing attention on the development of learning-augmented algorithms, we revisit the classical online traveling salesman problem (OLTSP) from the perspective of such learning approaches. A learning-augmented online algorithm, or simply an online algorithm with predictions, considers how to improve its competitive performance with theoretical guarantees by forecasting the information of future requests, e.g., their release time or locations in the OLTSP. In this study, we investigate the OLTSP on the real line, motivated by the parcel picking problem in a smart warehouse, which aims at scheduling a route for a server (saying, a Kiva robot), starting at the origin, serving all online requests and returning to the origin such that the completion time is minimized. Each online request is released over time on the real line and the server moves back and forth along the line with unit speed. We mainly focus on zealous algorithms, a special type of online algorithms for the OLTSP which never allow the sever to wait if there are still unserved requests, and exploit a specific forecasting strategy, called online predictions, which makes a sequence of predictions one by one in an online manner. In order to ensure better competitive performance, we particularly explore the worst-case scenarios that restrict the power of such predictions. Based on the discussion, we make an assumption in which online predictions are guaranteed to be useful, and devise a learning-augmented algorithm with max 6 λ + 1 4 λ , 2 λ + 1 2 λ -robustness and max 3 2 + η t + η p O P T , 6 + λ 4 + (1 − λ) η p O P T -consistency, 0 < λ ≤ 1 , comparing to the previous lower bound of 7 4 , where η t and η p which indicate prediction errors are sufficiently small constants. Moreover, we also conduct numerical experiments to demonstrate the practical effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

As one of Karp's 21 NP-complete problems, the subset sum problem, as well as its generalization, has been well studied. Among the rich literature, there is little work on the online version, where items arrive over list and irrevocable decisions on packing them or not must be made immediately. Under the online setting, no deterministic algorithms are competitive, while for randomized algorithms the best competitive ratio is 1/2. It is thus of great interest to improve the performance bounds for both deterministic and randomized algorithms, assuming predicted information is available in the learning-augmented model. Along this line, we revisit online subset sum by showing that, with learnable predictions, there exist learning-augmented algorithms to break through the worst-case bounds on competitive ratio. The theoretical results are also experimentally verified, where we come up with a new idea in designing experiments. Namely, we design neural networks to serve as adversaries, verifying the robustness of online algorithms. Under this framework, several networks are trained to select adversarial instances and the results show that our algorithms are competitive and robust. [ABSTRACT FROM AUTHOR]