检索结果-内蒙古大学图书馆

DISCRETE APPLIED MATHEMATICS 2023年 341卷 394-405页

作者： Bampis, Evripidis Escoffier, Bruno Youssef, Paul Sorbonne Univ CNRS LIP6 4 Pl Jussieu F-75005 Paris France Inst Univ France Paris France Univ Grenoble Alpes LIG F-38400 St Martin Dheres France

We focus on an online 2-stage problem, motivated by the following situation: consider a system where students shall be assigned to universities. There is a first round where some students apply, and a first (stable) matching M1 has to be computed. However, some students may decide to leave the system (change their plan, go to a foreign university, or to some institution not in the system). Then, in a second round (after these deletions), we shall compute a second (final) stable matching M2. As it is undesirable to change assignments, the goal is to minimize the number of divorces/modifications between the two stable matchings M1 and M2. Then, how should we choose M1 and M2? We show that there is an optimal online algorithm to solve this problem. In particular, thanks to a dominance property, we show that we can optimally compute M1 without knowing the students that will leave the system. We generalize the result to some other possible modifications in the input (i.e., in the sets of students and/or open positions in universities). We also tackle the case of more stages, showing that no competitive (online) algorithm can be achieved for the considered problem as soon as there are 3 stages.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Stable matching on-line algorithms 2-stage optimization

来源：评论

学校读者我要写书评

暂无评论

Picking Operations in Warehouses With Dynamically Arriving Orders: How Good is Reoptimization?

引用

NETWORKS 2025年

作者： Lorenz, Catherine Otto, Alena Gendreau, Michel Univ Passau Chair Management Sci Operat & Supply Chain Managem Passau Germany Tech Univ Munich Adv Analyt Mfg Management Heilbronn Germany Polytech Montreal Dept Math & Ind Engn Montreal PQ Canada Polytech Montreal CIRRELT Montreal PQ Canada

E-commerce operations are essentially online, with customer orders arriving dynamically. However, very little is known about the performance of online policies for warehousing with respect to optimality, particularly for order picking and batching operations, which constitute a substantial portion of the total operating costs in warehouses. We aim to close this gap for one of the most prominent dynamic algorithms, namely reoptimization (Reopt), which reoptimizes the current solution each time a new order arrives. We examine Reopt in the Online Order Batching, Sequencing, and Routing Problem (OOBSRP), in both cases when the picker uses either a manual pushcart or a robotic cart. Moreover, we examine the non-interventionist Reopt in the case of a manual pushcart, wherein picking instructions are provided exclusively at the depot. We establish analytical performance bounds employing worst-case and probabilistic analysis. We demonstrate that, under generic stochastic assumptions, Reopt is almost surely asymptotically optimal and, notably, we validate its near-optimal performance in computational experiments across a broad range of warehouse settings. These results underscore Reopt's relevance as a method for online warehousing applications.

关键词： competitive analysis on-line algorithms order batching and routing problem reoptimization warehouses

来源：评论

学校读者我要写书评

暂无评论

Improved exploration of unknown polygons

引用

THEORETICAL COMPUTER SCIENCE 2022年 922卷 424-437页

作者： Tan, Xuehou Wei, Qi Tokai Univ Sch Informat Sci & Technol 4-1-1 Kitakaname Hiratsuka Kanagawa 2591292 Japan Liaoning Normal Univ Sch Comp & Informat Technol South Liushu St 1 Dalian 116081 Peoples R China

We present an on-line strategy for a mobile robot to explore an unknown simple polygon P, so as to output a so-called watchman route such that every interior point of P is visible from at least one point along the route. The length of robot???s route is guaranteed to be at most 7 times that of the shortest watchman route that could be computed offline. This significantly improves upon the previously known 26.5-competitive strategy and confirms a conjecture due to Hoffmann et al. (2001) [10]. Our result is mainly obtained by implementing on-line a known off-line algorithm that approximates the shortest watchman route to a factor of root 2. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Computational geometry on-line algorithms Competitive strategy Watchman route problem Polygon exploration problem Angle hull

来源：评论

学校读者我要写书评

暂无评论

Lease or financial lease? Deterministic strategies for on-line financial lease problem with the second-hand transaction

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第2期44卷 1248-1264页

作者： Zhang, Yong Li, Jiahao Yang, Xingyu Wang, Xiaohui Guangdong Univ Technol Sch Management Guangzhou 510520 Guangdong Peoples R China Tianjin Univ Technol & Educ Sch Econ & Management Tianjin 300222 Peoples R China

The residual value of the equipment is an important and inevitable issue for any decision-making process of equipment leasing. In this paper, we present an on-line financial leasing problem considering the second-hand transaction issue, i.e. the equipment can be sold in the secondary market when it is no longer needed. Using competitive analysis, the optimal deterministic strategies are given to deal with the financial leasing problem. Finally, to test the performance of the proposed on-line financial leasing strategies, several numerical experiments are conducted.

关键词： Deterministic leasing strategy Financial lease Second-hand transaction Competitive analysis on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

An asymptotically tight online algorithm for m-Steiner Traveling Salesman Problem

引用

INFORMATION PROCESSING LETTERS 2022年 174卷

作者： Zhang, Yubai Zhang, Zhao Liu, Zhaohui Chen, Qirong East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Shangrao Normal Univ Coll Math & Comp Sci Shangrao 334001 Jiangxi Peoples R China

This paper studies the m-Steiner Traveling Salesman Problem with online edge blockages. Under the assumption that there might be some blockages on the roads which are non-recoverable in a short time, the goal of the Min-Max online m-Steiner Traveling Salesman problem (MinMax-mSTSP(online)) is to find m closed tours that visit each customer at least once such that the maximum cost of the m salesmen is as small as possible. We give an online algorithm and show that its competitive ratio is at most k-1/m + 10 for m >= 2 and k + 2 for m = 1, where k is the number of blockages. This ratio is asymptotically tight since a lower bound Left perpendicular k/m Right perpendicular + 1 for this problem has been obtained in [16]. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms on-line algorithms Steiner Traveling Salesman Problem Blockages

来源：评论

学校读者我要写书评

暂无评论

A nearly tight lower bound for the d-dimensional cow-path problem

引用

INFORMATION PROCESSING LETTERS 2023年 182卷

作者： Bansal, Nikhil Kuszmaul, John Kuszmaul, William Univ Michigan Ann Arbor MI USA Yale Univ New Haven CT USA MIT Cambridge MA 02139 USA

In the d-dimensional cow-path problem, a cow living in Rd must locate a (d - 1) -dimensional hyperplane H whose location is unknown. The only way that the cow can find H is to roam Rd until it intersects H. If the cow travels a total distance s to locate a hyperplane H whose distance from the origin was r > 1, then the cow is said to achieve competitive ratio s/r. It is a classic result that, in R2, the optimal (deterministic) competitive ratio is 9. In R3, the optimal competitive ratio is known to be at most ,-=1 13.811. But in higher dimensions, the asymptotic relationship between d and the optimal competitive ratio remains an open question. The best upper and lower bounds, due to Antoniadis et al., are O(d3/2) and S2(d), leaving a gap of roughly 4/d. In this note, we achieve a stronger lower bound of S2 similar to(d3/2).(c) 2023 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems Computational geometry on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for single machine scheduling problem with release dates and submodular penalties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第4期45卷 105-105页

作者： Liu, Xiaofei Xiao, Man Li, Weidong Zhu, Yaoyu Ma, Lei Yunnan Univ Sch Informat Sci & Engn Kunming 650504 Peoples R China Yunnan Univ Sch Math & Stat Kunming 650504 Peoples R China Peking Univ Sch Elect Engn & Comp Sci Beijing 100871 Peoples R China Beijing Acad Artificial Intelligence Beijing 100871 Peoples R China Peking Univ Natl Biomed Imaging Ctr Beijing 100871 Peoples R China

In this paper, we consider the single machine scheduling problem with release dates and submodular penalties, in which each job can be either assigned to the machine or rejected. The objective is to minimize the sum of the makespan of the processed jobs and the penalty of the rejected jobs which is determined by a submodular function. First, we present a simple algorithm for the off-line problem. Second, for the on-line problem, we prove that there is no on-line algorithm with a constant competitive ratio if the penalty submodular function is not monotone, and present an on-line algorithm with a competitive ratio of 3 if the penalty submodular function is monotone. Finally, we consider a special case of the on-line problem in which all jobs have the same release date. We prove that there is no on-line algorithm with a competitive ratio of root 5+1/2 approximate to 1.618, and the competitive ratio of the on-line algorithm we presented is 2.

关键词： Scheduling problem Submodular penalties on-line algorithms Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Online search for a hyperplane in high-dimensional Euclidean space

引用

INFORMATION PROCESSING LETTERS 2022年 177卷

作者： Antoniadis, Antonios Hoeksma, Ruben Kisfaludi-Bak, Sandor Schewior, Kevin Univ Twente Dept Appl Math Enschede Netherlands Aalto Univ Dept Comp Sci Espoo Finland Univ Cologne Dept Math & Comp Sci Cologne Germany

We consider the online search problem in which a server starting at the origin of a d-dimensional Euclidean space has to find an arbitrary hyperplane. The best-possible competitive ratio and the length of the shortest curve from which each point on the d dimensional unit sphere can be seen are within a constant factor of each other. We show that this length is in 1(d) & AND;O(d(3/2)).(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Sphere inspection Online search problem on-line algorithms Computational geometry Cow-path problem

来源：评论

学校读者我要写书评

暂无评论

A new upper bound on the work function algorithm for the k-server problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第2期39卷 509-518页

作者： Zhang, Wenming Cheng, Yongxi Northwest Univ Sch Econ & Management Xian 710127 Peoples R China Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China

The k-server problem was introduced by Manasse et al. (in: Proceedings of the 20th annual ACM symposium on theory of computing, Chicago, Illinois, USA, pp 322-333, 1988), and is one of the most famous and well-studied online problems. Koutsoupias and Papadimitriou (J ACM42(5):971-983, 1995) showed that the work function algorithm (WFA) has a competitive ratio of at most 2k - 1 for the k-server problem. In this paper, by proposing a potential function that is different from the one in Koutsoupias and Papadimitriou (1995), we show that the WFA has a competitive ratio of at most n - 1, where n is the number of points in the metric space. When n < 2k, this ratio is less than 2k - 1.

关键词： Competitive analysis k-server problem on-line algorithms Work function

来源：评论

学校读者我要写书评

暂无评论

Online leasing strategy for depreciable equipment considering opportunity cost

引用

INFORMATION PROCESSING LETTERS 2020年 162卷 105981-105981页

作者： Zhang, Yong Xian, Jiayi Huang, Menghu Guangdong Univ Technol Sch Management Guangzhou 510520 Guangdong Peoples R China

There are two options for the leasing problem, buying at a high price or leasing at a low price. Once you choose to purchase the resources, you lose the opportunity to invest in other financial assets for additional benefits, such as a risk-free return of the interest rate. Thus, opportunity cost is an important factor to consider in the leasing problem. Accounting for opportunity cost, this paper extends the online leasing strategy for depreciable equipment. By applying competitive analysis, the optimal competitive ratios of the deterministic and randomized strategies are obtained. The results of numerical examples show that a smaller competitive ratio can be obtained when considering opportunity cost, which illustrates that the introduction of the opportunity cost has a significant influence on both the deterministic and randomized strategies. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Online leasing strategy Depreciable equipment Opportunity cost Competitive analysis on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：