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

Optimal deterministic algorithms for some variants of online Quota Traveling Salesman Problem

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第3期238卷 735-740页

作者： Yu, Wei Liu, Zhaohui Bao, Xiaoguang E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Shanghai Ocean Univ Coll Informat Technol Shanghai 201306 Peoples R China

This paper is concerned with the online Quota Traveling Salesman Problem. Depending on the symmetry of the metric and the requirement for the salesman to return to the origin, four variants are analyzed. We present optimal deterministic algorithms for each variant defined on a general space, a real line, or a half-line. As a byproduct, an improved lower bound for a variant of online TSP on a half-line is also obtained. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Traveling salesman Quota TSP online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online Hierarchical Scheduling on Two Uniform Machines with Bounded Job Sizes

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2015年第5期32卷 1550032-1550032页

作者： Lu, Xinrong Liu, Zhaohui E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

This paper studies the online hierarchical scheduling problem on two uniform machines with bounded job sizes, where the first machine M-1 receives both low and high hierarchy jobs, while the second machine M-2 only receives high hierarchy jobs. The machines have a speed ratio of s (s >= 1), and M-2 runs faster. Jobs are revealed one by one, and before the current job is scheduled, we have no information about next jobs except that the size of any job is in the interval [1, t]. The objective is to minimize the makespan. We present optimal algorithms for all (s, t) pairs.

关键词： Hierarchical scheduling uniform machine online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online Adjoint Methods for Optimization of PDEs

引用

APPLIED MATHEMATICS AND OPTIMIZATION 2022年第2期85卷 1-29页

作者： Sirignano, Justin Spiliopoulos, Konstantinos Univ Oxford Math Inst Oxford England Boston Univ Dept Math & Stat Boston MA 02215 USA

We present and mathematically analyze an online adjoint algorithm for the optimization of partial differential equations (PDEs). Traditional adjoint algorithms would typically solve a new adjoint PDE at each optimization iteration, which can be computationally costly. In contrast, an online adjoint algorithm updates the design variables in continuous-time and thus constantly makes progress towards minimizing the objective function. The online adjoint algorithm we consider is similar in spirit to the the pseudo-time-stepping, one-shot method which has been previously proposed. Motivated by the application of such methods to engineering problems, we mathematically study the convergence of the online adjoint algorithm. The online adjoint algorithm relies upon a time-relaxed adjoint PDE which provides an estimate of the direction of steepest descent. The algorithm updates this estimate continuously in time, and it asymptotically converges to the exact direction of steepest descent as t -> infinity. We rigorously prove that the online adjoint algorithm converges to a critical point of the objective function for optimizing the PDE. Under appropriate technical conditions, we also prove a convergence rate for the algorithm. A crucial step in the convergence proof is a multi-scale analysis of the coupled system for the forward PDE, adjoint PDE, and the gradient descent ODE for the design variables.

关键词： online algorithm Adjoint algorithm Optimization Partial differential equations (PDEs)

来源：评论

学校读者我要写书评

暂无评论

Truthful online double auctions for on-demand integrated ride-sourcing platforms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期317卷 737-747页

作者： Ding, Xiaoshu Qi, Qi Jian, Sisi Hong Kong Univ Sci & Technol Dept Civil & Environm Engn Kowloon Clear Water Bay Hong Kong Peoples R China Renmin Univ China Gaoling Sch Artificial Intelligence Beijing Peoples R China

Integrated platforms are an emerging model of business that integrates ride-sourcing services provided by multiple companies on a single platform. It reduces market fragmentation and brings benefits to both travelers and participating independent transport service providers. To ensure the sustainability of such platforms, the main challenge lies in efficient matching between travelers and ride-sourcing companies, so that both sides obtain non-negative utility. In this study, we propose a double auction based framework to solve the matching and pricing problems for on-demand integrated ride-sourcing platforms. To solve the real-time matching problem, we develop two online mechanisms with a critical price dynamic updating algorithm and a greedy algorithm. The proposed mechanisms are guaranteed to achieve the desired economic properties, and their efficiency is evaluated through numerical studies.

关键词： Auction/bidding Demand responsive transport Integrated ride-sourcing platform Supply-demand matching online algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal semi-online preemptive algorithms for machine covering on two uniform machines

引用

THEORETICAL COMPUTER SCIENCE 2005年第2-3期339卷 293-314页

作者： He, Y Jiang, YW Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Zhejiang Univ State Key Lab CAD & CG Hangzhou 310027 Peoples R China

In this paper, we consider the semi-online preemptive scheduling problem with decreasing job sizes on two uniform machines. Our goal is to maximize the continuous period of time (starting from time zero) when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced before all the jobs are completed. We design optimal deterministic semi-online algorithms for every machine speed ratio s is an element of [1, infinity), and show that idle time is required during the assignment procedure of algorithms for any s > root 6/2. The competitive ratios of the algorithms match the randomized lower bound for every 1 <= s <= 3. The problem of whether randomization still does not help for the discussed preemptive scheduling problem remains open. (c) 2005 Elsevier B.V. All rights reserved.

关键词： online algorithm preemptive scheduling machine covering competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Hybrid online protocols for source location privacy in wireless sensor networks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2018年 115卷 67-81页

作者： Bradbury, Matthew Jhumka, Arshad Leeke, Matthew Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

Wireless sensor networks (WSNs) will form the building blocks of many novel applications such as asset monitoring. These applications will have to guarantee that the location of the occurrence of specific events is kept private from attackers, in what is called the source location privacy (SLP) problem. Fake sources have been used in numerous techniques, however, the solution's efficiency is typically achieved by fine-tuning parameters at compile time. This is undesirable as WSN conditions may change. In this paper, we first present an SLP algorithm - Dynamic - that estimates the relevant parameters at runtime and show that it provides a high level of SLP, albeit at the expense of a high number of messages. To address this, we provide a hybrid online algorithm - DynamicSPR - that uses directed random walks for the fake sources allocation strategy to reduce energy usage. We perform simulations of the various protocols we present and our results show that DynamicSPR provides a similar level of SLP as when parameters are optimised at compile-time, with a lower number of messages sent. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Wireless sensor networks Source location privacy Fake sources Random walks online algorithm

来源：评论

学校读者我要写书评

暂无评论

Image Alignment by online Robust PCA via Stochastic Gradient Descent

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2016年第7期26卷 1241-1250页

作者： Song, Wenjie Zhu, Jianke Li, Yang Chen, Chun Zhejiang Univ Coll Comp Sci Hangzhou 310027 Peoples R China

Aligning a given set of images is usually conducted in batch mode manner, which not only requires large amount of memory but also adjusts all the previous transformations to register an input image. To address this issue, we propose a novel approach to image alignment by incorporating the geometric transformation into online robust principal component analysis (PCA). Instead of calculating the warp update using noisy input samples like the conventional methods, we suggest directly linearizing the object function by performing warp update on the recovered samples, which corresponds to an efficient inverse composition algorithm. Since the basis matrix is kept constant for a given sample, both the latent vector and warp update can be very efficiently computed. Moreover, we present two basis updating methods for robust PCA, including the closed-form solution and stochastic gradient descent scheme. We have conducted the extensive experiments on the real-world tasks of background subtraction with camera motion and visual tracking on the challenging video sequences, whose promising results demonstrate the efficacy of our presented approach.

关键词： Image alignment online algorithm robust principal component analysis (PCA)

来源：评论

学校读者我要写书评

暂无评论

Improved lower bounds for the online bin packing problem with cardinality constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第1期29卷 67-87页

作者： Fujiwara, Hiroshi Kobayashi, Koji Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan

The bin packing problem has been extensively studied and numerous variants have been considered. The k-item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522-550, 1975). In addition to the formulation of the classical bin packing problem, this problem imposes a cardinality constraint that the number of items packed into each bin must be at most k. For the online setting of this problem, in which the items are given one by one, Babel et al. (Discret Appl Math 143: 238-251, 2004) provided lower boundsv root 2 approximate to 1.41421 and 1.5 on the asymptotic competitive ratio for k = 2 and 3, respectively. For k >= 4, some lower bounds (e.g., by van Vliet (Inf Process Lett 43:277-284, 1992) for the online bin packing problem, i.e., a problem without cardinality constraints, can be applied to this problem. In this paper we consider the online k-item bin packing problem. First, we improve the previous lower bound 1.41421 to 1.42764 for k = 2. Moreover, we propose a new method to derive lower bounds for general k and present improved bounds for various cases of k >= 4. For example, we improve 1.33333 to 1.5 for k = 4, and 1.33333 to 1.47058 for k = 5.

关键词： Bin packing problem online algorithm Competitive analysis Cardinality constraint

来源：评论

学校读者我要写书评

暂无评论

online Node- and Edge-Deletion Problems with Advice

引用

algorithmICA 2021年第9期83卷 2719-2753页

作者： Chen, Li-Hsuan Hung, Ling-Ju Lotze, Henri Rossmanith, Peter Pro Brand Int TW Inc Hsinchu Taiwan Natl Taipei Univ Business Taipei Taiwan Rhein Westfal TH Aachen Aachen Germany

In online edge- and node-deletion problems the input arrives node by node and an algorithm has to delete nodes or edges in order to keep the input graph in a given graph class Pi at all times. We consider only hereditary properties Pi, for which optimal online algorithms exist and which can be characterized by a set of forbidden subgraphs F and analyze the advice complexity of getting an optimal solution. We give almost tight bounds on the DELAYED CONNECTED F-NODE-DELETION PROBLEM, where all graphs of the family F have to be connected and almost tight lower and upper bounds for the DELAYED H-NODE-DELETION PROBLEM, where there is one forbidden induced subgraph H that may be connected or not. For the DELAYED H-NODE-DELETION PROBLEM the advice complexity is basically an easy function of the size of the biggest component in H. Additionally, we give tight bounds on the Delayed Connected F-Edge-Deletion Problem, where we have an arbitrary number of forbidden connected graphs. For the latter result we present an algorithm that computes the advice complexity directly from F. We give a separate analysis for the Delayed Connected H-Edge-Deletion Problem, which is less general but admits a bound that is easier to compute.

关键词： online algorithm Advice complexity Node-deletion Edge-deletion Delayed decision model Graph modification

来源：评论

学校读者我要写书评

暂无评论

online passive-aggressive algorithms

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2006年第3期7卷 551-585页

作者： Crammer, K Dekel, O Keshet, J Shalev-Shwartz, S Singer, Y Hebrew Univ Jerusalem Sch Comp Sci & Engn IL-91904 Jerusalem Israel

We present a family of margin based online learning algorithms for various prediction tasks. In particular we derive and analyze algorithms for binary and multiclass categorization, regression, uniclass prediction and sequence prediction. The update steps of our different algorithms are all based on analytical solutions to simple constrained optimization problems. This unified view allows us to prove worst-case loss bounds for the different algorithms and for the various decision problems based on a single lemma. Our bounds on the cumulative loss of the algorithms are relative to the smallest loss that can be attained by any fixed hypothesis, and as such are applicable to both realizable and unrealizable settings. We demonstrate some of the merits of the proposed algorithms in a series of experiments with synthetic and real data sets.

关键词： .online learning binary classification different algorithms constrained optimization online algorithm decision problems Shalev-Shwartz multiclass online Passive-Aggressive algorithms uniclass loss bounds PA algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：