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

priority algorithms with advice for disjoint path allocation problems

THEORETICAL COMPUTER SCIENCE 2024年 1021卷

作者： Bockenhauer, Hans-Joachim Frei, Fabian Horvath, Silvan Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany Swiss Fed Inst Technol Dept Math Zurich Switzerland

We analyze the Disjoint Path Allocation problem (DPA) in the priority framework. Motivated by the problem of traffic regulation in communication networks, DPA consists of allocating edge-disjoint paths in a graph. Like an online algorithm, a priority algorithm receives its input sequentially and must output irrevocable decisions for individual input items before having seen the entire input. However, in contrast to the online setting, a priority algorithm may choose an order on the set of all possible input items and the actual input is then presented according to this order. A priority algorithm is thus a natural model for the intuitively well-understood concept of a greedy algorithm. Mainly motivated by their application for proving lower bounds, we also consider priority algorithms with advice, thus measuring the necessary amount of information about the yet unknown parts of the input. Besides considering the classical variant of the DPA problem on paths and the related problem of Length-Weighted DPA, we mainly focus on DPA on trees. We show asymptotically matching upper and lower bounds on the advice necessary for optimality in LWDPA and generalize the known optimality result for DPA on paths to trees with maximal degree at most 3. On trees with higher maximal degree, we prove matching upper and lower bounds on the approximation ratio in the advice-free priority setting as well as upper and lower bounds on the advice necessary to achieve optimality.

关键词： Disjoint path allocation priority algorithms Advice complexity Greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

priority algorithms for graph optimization problems

引用

THEORETICAL COMPUTER SCIENCE 2010年第1期411卷 239-258页

作者： Borodin, Allan Boyar, Joan Larsen, Kim S. Mirmohammadi, Nazanin Univ So Denmark DK-5230 Odense M Denmark Univ Toronto Toronto ON M5S 1A1 Canada

We continue the study of priority or "greedy-like" algorithms as initiated in Borodin et al. (2003) [10] and as extended to graph theoretic problems in Davis and Impagliazzo (2009) [12]. Graph theoretic problems pose some modeling problems that did not exist in the original applications of Borodin et al. and Angelopoulos and Borodin (2002) [3]. Following the work of Davis and Impagliazzo, we further clarify these concepts. In the graph theoretic setting, there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known "greedy algorithms". (C) 2009 Elsevier B.V. All rights reserved.

关键词： Approximation algorithms priority algorithms Greedy algorithms Vertex cover Independent set Vertex coloring

来源：评论

学校读者我要写书评

暂无评论

Advice Complexity of priority algorithms

引用

THEORY OF COMPUTING SYSTEMS 2020年第4期64卷 593-625页

作者： Borodin, Allan Boyar, Joan Larsen, Kim S. Pankratov, Denis Univ Toronto Dept Comp Sci Toronto ON Canada Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Concordia Univ Dept Comp Sci & Software Engn Montreal PQ Canada

The priority model of "greedy-like" algorithms was introduced by Borodin, Nielsen, and Rackoff in 2002. We augment this model by allowing priority algorithms to have access to advice, i.e., side information precomputed by an all-powerful oracle. Obtaining lower bounds in the priority model without advice can be challenging and may involve intricate adversary arguments. Since the priority model with advice is even more powerful, obtaining lower bounds presents additional difficulties. We sidestep these difficulties by developing a general framework of reductions which makes lower bound proofs relatively straightforward and routine. We start by introducing the Pair Matching problem, for which we are able to prove strong lower bounds in the priority model with advice. We develop a template for constructing a reduction from Pair Matching to other problems in the priority model with advice - this part is technically challenging since the reduction needs to define a valid priority function for Pair Matching while respecting the priority function for the other problem. Finally, we apply the template to obtain lower bounds for a number of standard discrete optimization problems.

关键词： priority algorithms Advice complexity Greedy algorithms Optimization problems

来源：评论

学校读者我要写书评

暂无评论

Advice complexity of adaptive priority algorithms

引用

THEORETICAL COMPUTER SCIENCE 2024年 984卷

作者： Boyar, Joan Larsen, Kim S. Pankratov, Denis Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark Concordia Univ Dept Comp Sci & Software Engn 2155 Guy St Montreal PQ H3H 2L9 Canada

The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.

关键词： Greedy algorithms priority algorithms Adaptive priority algorithms Exact algorithms Online algorithms Advice complexity

来源：评论

学校读者我要写书评

暂无评论

(Incremental) priority algorithms

引用

ALGORITHMICA 2003年第4期37卷 295-326页

作者： Borodin, A Nielsen, MN Rackoff, C Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada Univ So Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark

We study the question of which optimization problems can be optimally or approximately solved by "greedy-like" algorithms. For definiteness, we limit the present discussion to some well-studied scheduling problems although the underlying issues apply in a much more general setting. Of course, the main benefit of greedy algorithms lies in both their conceptual simplicity and their computational efficiency. Based on the experience from online competitive analysis, it seems plausible that we should be able to derive approximation bounds for "greedy-like" algorithms exploiting only the conceptual simplicity of these algorithms. To this end, we need (and will provide) a precise definition of what we mean by greedy and greedy-like.

关键词： priority algorithms greedy algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

Optimal Charging Scheduling of Electric Vehicles in Micro Grids Using priority algorithms and Particle Swarm Optimization

引用

MOBILE NETWORKS & APPLICATIONS 2019年第6期24卷 1835-1847页

作者： Savari, George Fernandez Krishnasamy, Vijayakumar Sugavanam, Vidyasagar Vakesan, Kalyanasundaram SRM Inst Sci & Technol Dept Elect & Elect Engn Kattankulathur 603203 India

The large-scale integration of electric vehicles (EVs) into modern power grid brings both challenges and opportunities to the performance of the systems. This paper presents an optimal static (when EV is stationary) charging scheduling scheme of EVs to minimize the charging cost while complying with the constraints related to the status of the charging station. The proposed systematic charging scheme is based on "Particle Swarm Optimization (PSO)". It is compared with well-established algorithms such as "Arrival Time-Based priority (ATP) algorithm" and "SOC-Based priority (SBP) algorithm". In addition, a microgrid scenario is further considered for reducing the consumption of energy from the grid and also, reducing the charging cost by properly shifting the EV load. Based on the study carried out for a sample test cases considered, it is found that the proposed scheme has better performance compared to the existing schemes.

关键词： Charging stations Electric vehicles Microgrid Optimization priority algorithms

来源：评论

学校读者我要写书评

暂无评论

BubbleSearch: A simple heuristic for improving priority-based greedy algorithms

引用

INFORMATION PROCESSING LETTERS 2006年第4期97卷 161-169页

作者： Lesh, N Mitzenmacher, A Harvard Univ Dept Comp Sci Cambridge MA 02138 USA Mitsubishi Elect Res Labs Cambridge MA 02139 USA

We introduce BubbleScarch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign values to elements in some fixed or adaptively determined order. BubbleSearch extends priority algorithms by selectively considering additional orders near an initial good ordering. While many notions of nearness are possible, we explore algorithms based on the Kendall-tau distance (also known as the BubbleSort distance) between permutations. Our contribution is to elucidate the BubbleSearch paradigm and experimentally demonstrate its effectiveness. (c) 2005 Published by Elsevier B.V.

关键词： greedy algorithms priority algorithms randomized algorithms heuristic algorithms GRASP algorithms

来源：评论

学校读者我要写书评

暂无评论

Greedy Matching: Guarantees and Limitations

引用

ALGORITHMICA 2017年第1期77卷 201-234页

作者： Besser, Bert Poloczek, Matthias Goethe Univ Frankfurt Main Inst Informat Frankfurt Germany Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14850 USA

Since Tinhofer proposed the MINGREEDY algorithm for maximum cardinality matching in 1984, several experimental studies found the randomized algorithm to perform excellently for various classes of random graphs and benchmark instances. In contrast, only few analytical results are known. We show that MINGREEDY cannot improve on the trivial approximation ratio of 1/2 whp., even for bipartite graphs. Our hard inputs seem to require a small number of high-degree nodes. This motivates an investigation of greedy algorithms on graphs with maximum degree Delta: we show that MINGREEDY achieves a Delta-1/2 Delta-3-approximation for graphs with Delta=3 and for Delta-regular graphs, and a guarantee of Delta-1/2/2 Delta-2 for graphs with maximum degree Delta. Interestingly, our bounds even hold for the deterministic MINGREEDY that breaks all ties arbitrarily. Moreover, we investigate the limitations of the greedy paradigm, using the model of priority algorithms introduced by Borodin, Nielsen, and Rackoff. We study deterministic priority algorithms and prove a Delta-1/2 Delta-3 -inapproximability result for graphs with maximum degree Delta;thus, these greedy algorithms do not achieve a 1/2+epsilon-approximation and in particular the 2/3-approximation obtained by the deterministic MINGREEDY for Delta=3 is optimal in this class. For k-uniform hypergraphs we show a tight 1/k-inapproximability bound. We also study fully randomized priority algorithms and give a 5/6-inapproximability bound. Thus, they cannot compete with matching algorithms of other paradigms.

关键词： Maximum matching Greedy algorithms Approximation algorithms priority algorithms Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Characterizing sets of jobs that admit optimal greedy-like algorithms

引用

JOURNAL OF SCHEDULING 2010年第2期13卷 163-176页

作者： Papakonstantinou, Periklis A. Rackoff, Charles W. Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada

The "priority Algorithm" is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) priority algorithms, Algorithmica 37(4): 295-326, 2003) which formulates a wide class of greedy algorithms. For an arbitrary set S of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of S. In the case where the jobs are all intervals, we characterize such sets S and give an efficient algorithm (when S is finite) for determining this. We show that in general, however, the problem is NP-hard.

关键词： Scheduling Interval scheduling priority algorithms Optimal greedy algorithms Parallel scheduling

来源：评论

学校读者我要写书评

暂无评论

GREEDY algorithms FOR THE MAXIMUM SATISFIABILITY PROBLEM: SIMPLE algorithms AND INAPPROXIMABILITY BOUNDS

引用

SIAM JOURNAL ON COMPUTING 2017年第3期46卷 1029-1061页

作者： Poloczek, Matthias Schnitger, Georg Williamson, David P. Van Zuylen, Anke Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA Goethe Univ Frankfurt Main Inst Comp Sci Frankfurt Germany Coll William & Mary Dept Math Williamsburg VA 23185 USA

We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a 3/4-approximation in expectation. In contrast to previously known 3/4-approximation algorithms, our algorithm does not use flows or linear programming. Hence we provide a positive answer to a question posed by Williamson in 1998 on whether such an algorithm exists. Moreover, we show that Johnson's greedy algorithm cannot guarantee a 3/4-approximation, even if the variables are processed in a random order. Thereby we partially solve a problem posed by Chen, Friesen, and Zheng in 1999. In order to explore the limitations of the greedy paradigm, we use the model of priority algorithms of Borodin, Nielsen, and Rackoff. Since our greedy algorithm works in an online scenario where the variables arrive with their set of undecided clauses, we wonder if a better approximation ratio can be obtained by further fine-tuning its random decisions. For a particular information model we show that no priority algorithm can approximate Online MAX SAT within 3/4 + epsilon (for any epsilon > 0). We further investigate the strength of deterministic greedy algorithms that may choose the variable ordering. Here we show that no adaptive priority algorithm can achieve approximation ratio 3/4. We propose two ways in which this inapproximability result can be bypassed. First we show that if our greedy algorithm is additionally given the variable assignments of an optimal solution to the canonical LP relaxation, then we can derandomize its decisions while preserving the overall approximation guarantee. Second we give a simple, deterministic algorithm that performs an additional pass over the input. We show that this 2-pass algorithm satisfies clauses with a total weight of at least 3/4 OPTLP, where OPTLP is the objective value of the canonical linear program. Moreover, we demonstrate that our analysis is tight and detail how each pass can be implemented in linear time.

关键词： approximation algorithms greedy algorithms maximum satisfiability problem priority algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：