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

greedy algorithms for the profit-aware social team formation problem

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期44卷 94-118页

作者： Liu, Shengxin Poon, Chung Keung Harbin Inst Technol Shenzhen Sch Comp Sci & Technol Shenzhen Peoples R China Hang Seng Univ Hong Kong Dept Comp Hong Kong Peoples R China

Motivated by applications in online labor markets, we study the problem of forming multiple teams of experts in a social network to accomplish multiple tasks that require different combinations of skills. Our goal is to maximize the total profit of tasks that are completed by these teams subject to the capacity constraints of the experts. We study both the offline and online settings of the problem. For the offline problem, we present a simple and practical algorithm that improves upon previous results in many situations. For the online problem, we design competitive deterministic and randomized online algorithms. These are complemented by some hardness results in both settings.

关键词： Team formation greedy algorithms Social networks Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Optimal Utility Design of greedy algorithms in Resource Allocation Games

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第10期69卷 6592-6604页

作者： Konda, Rohit Chandan, Rahul Grimsman, David Marden, Jason R. Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA Brigham Young Univ Dept Comp Sci Provo UT 84602 USA

Designing fast, distributed algorithms for multiagent problems is vital for many novel application domains. greedy algorithms have been shown in many multiagent contexts to be an efficient approach to arrive at good solutions quickly. In this work, we ask the following: Is there any way to improve the performance of greedy algorithms without sacrificing the linear run-time guarantees? For this, we take inspiration from incentive design in the game-theoretic literature. In this work, we consider a modified version of the greedy algorithm where agents do not optimize against the global objective. Instead, each agent is prescribed an auxiliary utility function (which may differ from the original objective function) in which it optimizes under. By designing the utility functions properly, we show in this work that the resulting performance guarantees of the greedy algorithm can increase significantly. We study this approach in the context of resource-allocation games, which are used to model a rich variety of engineering applications. Interestingly, the performance guarantees from the modified greedy algorithm can be significantly close to the best centralized performance guarantees. The main technical contribution of the article is the characterization of the performance guarantees through a linear program construction.

关键词： greedy algorithms Games Resource management Standards Distributed algorithms Wireless communication Task analysis Algorithm design distributed systems game theory optimization resource allocation

来源：评论

学校读者我要写书评

暂无评论

Parallel greedy algorithms for Steiner Forest

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2025年第6期36卷 1311-1325页

作者： Ghalami, Laleh Grosu, Daniel Wayne State Univ Detroit MI 48202 USA

The Steiner Forest Problem is a fundamental combinatorial optimization problem in operations research and computer science. Given an undirected graph with non-negative weights for edges and a set of pairs of vertices called terminals, the Steiner Forest Problem is to find the minimum cost subgraph that connects each of the terminal pairs together. We design a family of parallel greedy algorithms based on a sequential heuristic greedy algorithm called Paired greedy, which iteratively connects the terminal pairs that have the minimum distance. The family of parallel algorithms consists of a set of algorithms exhibiting various degrees of parallelism determined by the number of pairs that are connected in parallel in each iteration of the algorithms. We implement and run the algorithms on a multi-core system and perform an extensive experimental analysis. We analyzed the performance of the algorithms on a rich library of Steiner Forest instances with various underlying graph types. The results show that our proposed parallel algorithms achieve significant speedup with respect to the sequential Paired greedy algorithm and provide solutions with costs that are very close to those of the solutions obtained by the sequential Paired greedy algorithm. We provide recommendation on selecting the type of parallel algorithm and its parameters in order to achieve the most efficient results for each class of instances.

关键词： Forestry greedy algorithms Costs Parallel algorithms Steiner trees Approximation algorithms Training Partitioning algorithms Optimization Libraries Steiner forest parallel algorithms multi-core

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Multi-Fidelity Sensor Selection: greedy algorithms to Place Cheap and Expensive Sensors With Cost Constraints

引用

IEEE SENSORS JOURNAL 2021年第1期21卷 600-611页

作者： Clark, Emily Brunton, Steven L. Kutz, J. Nathan Univ Washington Dept Phys Seattle WA 98195 USA Univ Washington Dept Mech Engn Seattle WA 98195 USA Univ Washington Dept Appl Math Seattle WA 98195 USA

We develop greedy algorithms to approximate the optimal solution to the multi-fidelity sensor selection problem, which is a cost constrained optimization problem prescribing the placement and number of cheap (low signal-to-noise) and expensive (high signal-to-noise) sensors in an environment or state space. Specifically, we evaluate the composition of cheap and expensive sensors, along with their placement, required to achieve accurate reconstruction of a high-dimensional state. We use the column-pivoted QR decomposition to obtain preliminary sensor positions. How many of each type of sensor to use is highly dependent upon the sensor noise levels, sensor costs, overall cost budget, and the singular value spectrum of the data measured. Such nuances allow us to provide sensor selection recommendations based on computational results for asymptotic regions of parameter space. We also present a systematic exploration of the effects of the number of modes and sensors on reconstruction error when using one type of sensor. Our extensive exploration of multi-fidelity sensor composition as a function of data characteristics is the first of its kind to provide guidelines towards optimal multi-fidelity sensor selection.

关键词： Sensor phenomena and characterization Noise level Sensor systems Matrix decomposition Noise measurement Guidelines Computational and artificial intelligence computational intelligence computation theory greedy algorithms sensors sensor phenomena and characterization sensor systems and applications sensor arrays signal processing noise additive noise

来源：评论

学校读者我要写书评

暂无评论

Execution Order Matters in greedy algorithms with Limited Information

Execution Order Matters in Greedy Algorithms with Limited In...

引用

American Control Conference (ACC)

作者： Konda, Rohit Grimsman, David Marden, Jason R. Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA Brigham Young Univ Dept Comp Sci Provo UT 84602 USA

ISBN: (数字)9781665451963

ISBN: (纸本)9781665451963

In this work, we study the multi-agent decision problem where agents try to coordinate to optimize a given system-level objective. While solving for the global optimum is intractable in many cases, the greedy algorithm is a wellstudied and efficient way to provide good approximate solutions - notably for submodular optimization problems. Executing the greedy algorithm requires the agents to be ordered and execute a local optimization based on the solutions of the previous agents. However, in limited information settings, passing the solution from the previous agents may be nontrivial, as some agents may not be able to directly communicate with each other. Thus the communication time required to execute the greedy algorithm is closely tied to the order that the agents are given. In this work, we characterize interplay between the communication complexity and agent orderings by showing that the complexity using the best ordering is O (n) and increases considerably to O (n(2)) when using the worst ordering. Motivated by this, we also propose an algorithm that can find an ordering and execute the greedy algorithm quickly, in a distributed fashion. We also show that such an execution of the greedy algorithm is advantageous over current methods for distributed submodular maximization.

关键词： greedy algorithms Complexity theory Communication networks Optimization

来源：评论

学校读者我要写书评

暂无评论

QUANTUM-ASSISTED greedy algorithms

QUANTUM-ASSISTED GREEDY ALGORITHMS

引用

IEEE International Geoscience and Remote Sensing Symposium (IGARSS)

作者： Ayanzadeh, Ramin Dorband, John Halem, Milton Finin, Tim Georgia Inst Technol Atlanta GA 30332 USA Univ Maryland Baltimore Cty Baltimore MD 21250 USA

ISBN: (数字)9781665427920

ISBN: (纸本)9781665427920

We show how to leverage quantum annealers (QAs) to better select candidates in greedy algorithms. Unlike conventional greedy algorithms that employ problem-specific heuristics for making locally optimal choices at each stage, we use QAs that sample from the ground state of a problem-dependent Hamiltonians at cryogenic temperatures and use retrieved samples to estimate the probability distribution of problem variables. More specifically, we look at each spin of the Ising model as a random variable and contract all problem variables whose corresponding uncertainties are negligible. Our empirical results on a D-Wave 2000Q quantum processor demonstrate that the proposed quantum-assisted greedy algorithm (QAGA) scheme can find notably better solutions compared to the state-of-the-art techniques in the realm of quantum annealing.

关键词： greedy algorithms Optimization Quantum Annealing Quantum Computing

来源：评论

学校读者我要写书评

暂无评论

Actuator Placement Under Structural Controllability Using Forward and Reverse greedy algorithms

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第12期66卷 5845-5860页

作者： Guo, Baiwei Karaca, Orcun Summers, Tyler Kamgarpour, Maryam Ecole Polytech Fed Lausanne Automat Control Lab CH-1015 Lausanne Switzerland Swiss Fed Inst Technol Automat Control Lab D ITET Zurich Switzerland UT Dallas Dept Mech Engn Richardson TX 75080 USA Univ British Columbia Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

Actuator placement is an active field of research, which has received significant attention for its applications in complex dynamical networks. In this article, we study the problem of finding a set of actuator placements minimizing the metric that measures the average energy consumed for state transfer by the controller, while satisfying a structural controllability requirement and a cardinality constraint on the number of actuators allowed. As no computationally efficient methods are known to solve such combinatorial set function optimization problems, two greedy algorithms, forward and reverse, are proposed to obtain approximate solutions. We first show that the constraint sets these algorithms explore can be characterized by matroids. We then obtain performance guarantees for the forward and reverse greedy algorithms applied to the general class of matroid optimization problems by exploiting properties of the objective function such as the submodularity ratio and the curvature. Finally, we propose feasibility check methods for both algorithms based on maximum flow problems on certain auxiliary graphs originating from the network graph. Our results are verified with case studies over large networks.

关键词： Actuators greedy algorithms Controllability Measurement Linear programming Optimization Energy consumption Actuator placement dynamical networks greedy algorithms structural controllability

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：