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

Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem

JOURNAL OF HEURISTICS 2009年第4期15卷 331-349页

作者： Gortz, Simon Klose, Andreas Univ Aarhus Dept Math Sci DK-8000 Aarhus C Denmark Univ Wuppertal Fac Econ & Social Sci D-42197 Wuppertal Germany

The single-sink fixed-charge transportation problem (SSFCTP) consists of finding a minimum cost flow from a number of nodes to a single sink. Beside a cost proportional to the amount shipped, the flow cost encompass a fixed charge. The SSFCTP is an important subproblem of the well-known fixed-charge transportation problem. Nevertheless, just a few methods for solving this problem have been proposed in the literature. In this paper, some greedy heuristic solutions methods for the SSFCTP are investigated. It is shown that two greedy approaches for the SSFCTP known from the literature can be arbitrarily bad, whereas an approximation algorithm proposed in the literature for the binary min-knapsack problem has a guaranteed worst case bound if adapted accordingly to the case of the SSFCTP.

关键词： Fixed-charge transportation problem Min-knapsack problem greedy algorithms Worst-case analysis Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第2期230卷 212-225页

作者： Glover, Fred OptTek Syst Inc Boulder CO 80302 USA

New variants of greedy algorithms, called advanced greedy algorithms, are identified for knapsack and covering problems with linear and quadratic objective functions. Beginning with single-constraint problems, we provide extensions for multiple knapsack and covering problems, in which objects must be allocated to different knapsacks and covers, and also for multi-constraint (multi-dimensional) knapsack and covering problems, in which the constraints are exploited by means of surrogate constraint strategies. In addition, we provide a new graduated-probe strategy for improving the selection of variables to be assigned values. Going beyond the greedy and advanced greedy frameworks, we describe ways to utilize these algorithms with multi-start and strategic oscillation metaheuristics. Finally, we identify how surrogate constraints can be utilized to produce inequalities that dominate those previously proposed and tested utilizing linear programming methods for solving multi-constraint knapsack problems, which are responsible for the current best methods for these problems. While we focus on 0-1 problems, our approaches can readily be adapted to handle variables with general upper bounds. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Metaheuristics greedy algorithms Knapsack/covering problems Surrogate constraints Multi-start/strategic oscillation Tabu search

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms make efficient mechanisms 15

Greedy algorithms make efficient mechanisms

引用

16th ACM Conference on Economics and Computation, EC 2015

作者： Lucier, Brendan Syrgkanis, Vasilis Microsoft Research CambridgeMA United States

ISBN: (纸本)9781450334105

We study mechanisms that use greedy allocation rules and pay-your-bid pricing to allocate resources subject to a matroid constraint. We show that all such mechanisms obtain a constant fraction of the optimal welfare at any equilibrium of bidder behavior, via a smoothness argument. This unifies numerous recent results on the price of anarchy of simple auctions. Our results extend to polymatroid and matching constraints, and we discuss extensions to more general matroid intersections.

关键词： greedy algorithms auctions mechanism design matroids price of anarchy

来源：评论

学校读者我要写书评

暂无评论

Sparse Approximation and Recovery by greedy algorithms

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第7期60卷 3989-4000页

作者： Livshitz, Eugene D. Temlyakov, Vladimir N. Evernote Corp Moscow 121087 Russia Moscow MV Lomonosov State Univ Moscow 121087 Russia Univ S Carolina Columbia SC 29208 USA Steklov Inst Math Moscow 119991 Russia

We study sparse approximation by greedy algorithms. Our contribution is twofold. First, we prove exact recovery with high probability of random K-sparse signals within [K(1+ epsilon)] iterations of the orthogonal matching pursuit (OMP). This result shows that in a probabilistic sense, the OMP is almost optimal for exact recovery. Second, we prove the Lebesgue-type inequalities for the weak Chebyshev greedy algorithm, a generalization of the weak orthogonal matching pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space setting. However, even in the case of a Hilbert space, our results add some new elements to known results on the Lebesgue-type inequalities for the restricted isometry property dictionaries. Our technique is a development of the recent technique created by Zhang.

关键词： greedy algorithms orthogonal matching pursuit sparse approximation Lebesgue-type inequality probability

来源：评论

学校读者我要写书评

暂无评论

Heuristic Scheduling of Batch Production Processes Based on Petri Nets and Iterated greedy algorithms

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2022年第1期19卷 251-261页

作者： Zhao, Ziyan Liu, Shixin Zhou, Mengchu You, Dan Guo, Xiwang Northeastern Univ State Key Lab Synthet Automat Proc Ind Shenyang 110819 Peoples R China Northeastern Univ Coll Informat Sci & Engn Shenyang 110819 Peoples R China New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Macau Univ Sci & Technol Inst Syst Engn Macau 999078 Peoples R China Macau Univ Sci & Technol Collaborat Lab Intelligent Sci & Syst Macau 999078 Peoples R China Univ Cagliari Dept Elect & Elect Engn I-09123 Cagliari Italy Liaoning Shihua Univ Comp & Commun Engn Coll Fushun 113001 Peoples R China

Wire rod and bar rolling is an important batch production process in steel production systems. A scheduling problem originated from this process is studied in this work by considering the constraints on sequence-dependent family setup time and release time. For each serial batch to be scheduled, it contains several jobs and the number of late jobs within it varies with its start time. First, we model a rolling process using a Petri net (PN), where a so-called rolling transition describes a rolling operation of a batch. The objective of the concerned problem is to determine a firing sequence of all rolling transitions such that the total number of late jobs is minimal. Next, a mixed-integer linear program is formulated based on the PN model. Due to the NP-hardness of the concerned problem, iterated greedy algorithm (IGA)-based methods by using different neighborhood structures and integrating a variable neighborhood descent method are developed to obtain its near-optimal solutions. To test the accuracy, speed, and stability of the proposed algorithms, we compare their solutions of different-size instances with those of CPLEX (a commercial software) and four heuristic peers. The results indicate that the proposed algorithms outperform their peers and have great potential to be applied to industrial production process scheduling. Note to Practitioners-This work deals with a scheduling problem of a batch production process, i.e., wire rod and bar rolling, which is modeled by a Petri net (PN). Due to the NP-hardness of the concerned problem, four iterated greedy algorithm-based methods are developed to solve it. The proposed methods are validated and tested by comparing their solutions with those of four heuristic peers and the exact ones (when available via CPLEX). Extensive experimental results show that they can fast solve one-week-scale instances with better performance than their peers', thereby proving the readiness to put them in industrial use. When solving a one

关键词： Job shop scheduling Task analysis Single machine scheduling Petri nets greedy algorithms Batch production process iterated greedy algorithm (IGA) Petri net (PN) variable neighborhood descent (VND)

来源：评论

学校读者我要写书评

暂无评论

Some greedy algorithms for sparse polynomial chaos expansions

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2019年第0期387卷 303-325页

作者： Baptista, Ricardo Stolbunov, Valentin Nair, Prasanth B. Univ Toronto Inst Aerosp Studies Toronto ON M3H 5T6 Canada MIT 77 Massachusetts Ave Cambridge MA 02139 USA

Compressed sensing algorithms approximate functions using limited evaluations by searching for a sparse representation among a dictionary of basis functions. Orthogonal matching pursuit (OMP) is a greedy algorithm for selecting basis functions whose computational cost scales with the size of the dictionary. For polynomial chaos (PC) approximations, the size of the dictionary grows quickly with the number of model inputs and the maximum polynomial degree, making them often prohibitive to use with greedy methods. We propose two new algorithms for efficiently constructing sparse PC expansions for problems with high-dimensional inputs. The first algorithm is a parallel OMP method coupled with an incremental QR factorization scheme, wherein the model construction step is interleaved with a nu-fold cross-validation procedure. The second approach is a randomized greedy algorithm that leverages a probabilistic argument to only evaluate a subset of basis functions from the dictionary at each iteration of the incremental algorithm. The randomized algorithm is demonstrated to recover model outputs with a similar level of sparsity and accuracy as OMP, but with a cost that is independent of the dictionary size. Both algorithms are validated with a numerical comparison of their performance on a series of algebraic test problems and PDEs with high-dimensional inputs. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Polynomial chaos greedy algorithms Uncertainty quantification Compressed sensing Stochastic models

来源：评论

学校读者我要写书评

暂无评论

ON greedy algorithms FOR SERIES-PARALLEL GRAPHS

引用

MATHEMATICAL PROGRAMMING 1988年第2期40卷 197-204页

作者： HOFFMAN, AJ 1.Department of Mathematical Sciences IBM Thomas J. Watson Research Center P.O. Box 218 10598 Yorktown Heights NY USA

This note describes some sufficient conditions for the maximum or minimum of a weighted flow (the weights are on paths, and are derived from weights on the edges of the path), of given volume in a series parallel grap... 详细信息

关键词： greedy algorithms series parallel graphs linear programming

来源：评论

学校读者我要写书评

暂无评论

Iterated greedy algorithms for Flow-Shop Scheduling Problems: A Tutorial

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2022年第3期19卷 1941-1959页

作者： Zhao, ZiYan Zhou, MengChu Liu, ShiXin Northeastern Univ State Key Lab Synthet Automat Proc Ind Shenyang 110819 Peoples R China Northeastern Univ Coll Informat Sci & Engn Shenyang 110819 Peoples R China New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Macau Univ Sci & Technol Inst Syst Engn Macau 999078 Peoples R China Macau Univ Sci & Technol Collaborat Lab Intelligent Sci & Syst Macau 999078 Peoples R China

An iterated greedy algorithm (IGA) is a simple and powerful heuristic algorithm. It is widely used to solve flow-shop scheduling problems (FSPs), an important branch of production scheduling problems. IGA was first developed to solve an FSP in 2007. Since then, various FSPs have been tackled by using IGA-based methods, including basic IGA, its variants, and hybrid algorithms with IGA integrated. Up until now, over 100 articles related to this field have been published. However, to the best of our knowledge, there is no existing tutorial or review paper of IGA. Thus, we focus on FSPs and provide a tutorial and comprehensive literature review of IGA-based methods. First, we introduce a framework of basic IGA and give an example to clearly show its procedure. To help researchers and engineers learn and apply IGA to their FSPs, we provide an open platform to collect and share related materials. Then, we make classifications of the solved FSPs according to their scheduling scenarios, objective functions, and constraints. Next, we classify and introduce the specific methods and strategies used in each phase of IGA for FSPs. Besides, we summarize IGA variants and hybrid algorithms with IGA integrated, respectively. Finally, we discuss the current IGA-based methods and already-solved FSP instances, as well as some important future research directions according to their deficiency and open issues.

关键词： Tutorials Job shop scheduling Search methods Optimization Linear programming Heuristic algorithms greedy algorithms Flow-shop scheduling problem (FSP) heuristic algorithm iterated greedy algorithm (IGA) review tutorial

来源：评论

学校读者我要写书评

暂无评论

greedy algorithms as locally stratified logic programs 22

Greedy algorithms as locally stratified logic programs

引用

22nd Italian Symposium on Advanced Database Systems, SEBD 2014

作者： Zaniolo, Carlo University of California Los Angeles United States

ISBN: (纸本)9781634391450

The problem of expressing and supporting classical greedy algorithms in Datalog has been the focus of significant research efforts that have produced very interesting specific solutions. But we still lack general treatments that characterize the relation of greedy algorithms to non-monotonic theories and lead to asymptotically optimal implementations. In this paper, we propose a very general solution that begins by identifying a class of locally stratified programs that is a perfect match for greedy algorithms, and leads to simple implementations that achieve optimal asymptotic complexities for well-know greedy algorithms.

关键词： Aggregates Datalog greedy algorithms Horn clauses

来源：评论

学校读者我要写书评

暂无评论

GRAPH SPARSIFICATION BY UNIVERSAL greedy algorithms

引用

Journal of Computational Mathematics 2023年第4期41卷 741-770页

作者： Ming-Jun Lai Jiaxin Xie Zhiqiang Xu Department of Mathematics University of GeorgiaAthensGA 30602USA LMIB of the Ministry of Education School of Mathematical SciencesBeihang UniversityBeijing 100191China LSEC Inst.Comp.Math.Academy of Mathematics and System ScienceChinese Academy of SciencesBeijing 100091China School of Mathematical Sciences University of Chinese Academy of SciencesBeijing 100049China

Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications,such as simplification of social networks,least squares problems,and numerical solution of symmetric positive definite linear *** this paper,inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit(OMP),we introduce a deterministic,greedy edge selection algorithm,which is called the universal greedy approach(UGA)for the graph sparsification *** a general spectral sparsification problem,e.g.,the positive subset selection problem from a set of m vectors in R n,we propose a nonnegative UGA algorithm which needs O(mn^(2)+n^(3)/ϵ^(2))time to find a 1+ϵ/β/1-ϵ/β-spectral sparsifier with positive coefficients with sparsity at most[n/ϵ^(2)],where β is the ratio between the smallest length and largest length of the *** convergence of the nonnegative UGA algorithm is *** the graph sparsification problem,another UGA algorithm is proposed which can output a 1+O(ϵ)/1-O(ϵ)-spectral sparsifier with[n/ϵ^(2)]edges in O(m+n^(2)/ϵ^(2))time from a graph with m edges and n vertices under some mild *** is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking *** best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear,i.e.O(m^(1+o(1)))for some o(1)=O((log log(m))^(2/3)/log^(1/3)(m)).Finally,extensive experimental results,including applications to graph clustering and least squares regression,show the effectiveness of proposed approaches.

关键词： Spectral sparsification Subset selection greedy algorithms Graph clustering Linear sketching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：