Log in

Relevant bibliographies by topics / Greedy Algorithms / Journal articles

To see the other types of publications on this topic, follow the link: Greedy Algorithms.

Journal articles on the topic 'Greedy Algorithms'

Author: Grafiati

Published: 4 June 2021

Last updated: 7 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Greedy Algorithms.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Abdallah, Alaa E., Mohammad Bsoul, Emad E. Abdallah, Ibrahim Al–Oqily, and George Kao. "Cluster-Based Online Routing Protocols for Ad Hoc Network." International Journal of Information Technology and Web Engineering 9, no. 4 (October 2014): 54–66. http://dx.doi.org/10.4018/ijitwe.2014100105.

Full text

Abstract:

In geographical routing algorithms, mobile nodes rely on geographical position to make routing judgments. Researchers frequently discuss such routing algorithms in (2D) space. However, in reality, mobile nodes spread in (3D) space. In this paper the authors present four new 3D geographical-based routing algorithms Cylinder, Greedy-Cylinder, Cluster-Cylinder, and Greedy-cluster-Cylinder. In Cylinder routing, the nodes are locally projected on the inner surface of a cylinder, perimeter routing is executed after that. Greedy-Cylinder starts with Greedy routing algorithm until a local minimum is reached. The algorithm then switches to Cylinder routing. Cluster-Cylinder elects a dominating set for all nodes and then uses this set for projection and routing. The fourth algorithm Greedy-cluster-Cylinder is a combination between Greedy-Cylinder and Cluster-Cylinder. The authors evaluate their new algorithms and compare them with many classical known algorithms. The simulation outcomes show the substantial enhancement in delivery rate over other algorithms.

APA, Harvard, Vancouver, ISO, and other styles

2

Ochkov, V. F., A. O. Ivanova, and M. D. Alekseev. "THREE "GREEDY" ALGORITHMS." Informatics in school, no. 9 (December 20, 2018): 34–42. http://dx.doi.org/10.32517/2221-1993-2018-17-9-34-42.

Full text

Abstract:

The article considers three logistic tasks (transportation problem, traveling salesman problem, pursuit problem), by the example of which the essence and features of “greedy” algorithms are shown. For the frst time, a solution was given to a transportation problem in the Mathcad Prime environment using the matrix method using units of measure. Two new applications of the traveling salesman problem have been proposed. The diﬀerence scheme for solving the pursuit problem is described.

APA, Harvard, Vancouver, ISO, and other styles

3

Lutoborski, Adam, and Vladimir N. Temlyakov. "Vector greedy algorithms." Journal of Complexity 19, no. 4 (August 2003): 458–73. http://dx.doi.org/10.1016/s0885-064x(03)00026-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Simmons, Benno I., Christoph Hoeppke, and William J. Sutherland. "Beware greedy algorithms." Journal of Animal Ecology 88, no. 5 (March 15, 2019): 804–7. http://dx.doi.org/10.1111/1365-2656.12963.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Tian, Heng, Fuhai Duan, Yong Sang, and Liang Fan. "Novel algorithms for sequential fault diagnosis based on greedy method." Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability 234, no. 6 (May 2, 2020): 779–92. http://dx.doi.org/10.1177/1748006x20914498.

Full text

Abstract:

Test sequencing for binary systems is a nondeterministic polynomial-complete problem, where greedy algorithms have been proposed to find the solution. The traditional greedy algorithms only extract a single kind of information from the D-matrix to search the optimal test sequence, so their application scope is limited. In this study, two novel greedy algorithms that combine the weight index for fault detection with the information entropy are introduced for this problem, which are defined as the Mix1 algorithm and the Mix2 algorithm. First, the application scope for the traditional greedy algorithms is demonstrated in detail by stochastic simulation experiments. Second, two new heuristic formulas are presented, and their scale factors are determined. Third, an example is used to show how the two new algorithms work, and four real-world D-matrices are employed to validate their universality and stability. Finally, the application scope of the Mix1 and Mix2 algorithms is determined based on stochastic simulation experiments, and the two greedy algorithms are also used to improve a multistep look-ahead heuristic algorithm. The Mix1 and Mix2 algorithms can obtain good results in a reasonable time and have a wide application scope, which also can be used to improve the multistep look-ahead heuristic algorithm.

APA, Harvard, Vancouver, ISO, and other styles

6

Hignasari, L. Virginayoga. "Komparasi Algoritma Cheapest Insertion Heuristic (CIH) Dan Greedy Dalam Optimasi Rute Pendistribusian Barang." Jurnal Ilmiah Vastuwidya 2, no. 2 (June 16, 2020): 31–39. http://dx.doi.org/10.47532/jiv.v2i2.87.

Full text

Abstract:

This study was aimed to compare algorithms that can effectively provide better solutions related to the problem of determining the shortest route in the distribution of goods. This research was a qualitative research. The object of research was the route of shipping goods of a business that is engaged in printing and convection. The algorithms compared in this study were Cheapest Insertion Heuristic (CIH) and Greedy algorithms. Both algorithms have advantages and disadvantages in finding the shortest route. From the results of the analysis using these two algorithms, the Cheapest Insertion Heuristic (CIH) and Greedy algorithm can provide almost the same optimization results. The difference was only the selection of the journey. The strength of the Greedy algorithm was that the calculation steps are simpler than the Cheapest Insertion Heuristic (CIH) algorithm. While the disadvantage of the Greedy algorithm was that it is inappropriate to find the shortest route with a relatively large number of places visited. The advantage of the Cheapest Insertion Heuristic (CIH) algorithm was that this algorithm is still stable, used for the relatively large number of places visited. While the lack of Cheapest Insertion Heuristic (CIH) algorithm was a complicated principle of calculation and was relatively longer than the Greedy algorithm.

APA, Harvard, Vancouver, ISO, and other styles

7

Ni, Qiufen, Chuanhe Huang, Panos M. Pardalos, Jia Ye, and Bin Fu. "Different Approximation Algorithms for Channel Scheduling in Wireless Networks." Mobile Information Systems 2020 (November 16, 2020): 1–13. http://dx.doi.org/10.1155/2020/8836517.

Full text

Abstract:

We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parameters f , g . We present a series of simple and practical-for-implementation greedy algorithms which give constant factor approximation in both sides. First, we propose four approximation algorithms for the weighted channel allocation problem: 1. a greedy algorithm for the multichannel with fixed interference radius scheduling problem is proposed and an one side O 1 -IS-approximation is obtained; 2. a greedy O 1 , O 1 -approximation algorithm for single channel with fixed interference radius scheduling problem is presented; 3. we improve the existing algorithm for the multichannel scheduling and show an E O d / ε time 1 − ϵ -approximation algorithm; 4. we speed up the polynomial time approximation scheme for single-channel scheduling through merging two algorithms and show a 1 − ϵ , O 1 -approximation algorithm. Next, we study two polynomial time constant factor greedy approximation algorithms for the unweighted channel allocation with variate interference radius. A greedy O 1 -approximation algorithm for the multichannel scheduling problem and an O 1 , O 1 -approximation algorithm for single-channel scheduling problem are developed. At last, we do some experiments to verify the effectiveness of our proposed methods.

APA, Harvard, Vancouver, ISO, and other styles

8

WANG, LIN. "FAST ALGORITHMS FOR THERMAL-AWARE FLOORPLANNING." Journal of Circuits, Systems and Computers 23, no. 07 (June 2, 2014): 1450098. http://dx.doi.org/10.1142/s0218126614500984.

Full text

Abstract:

Thermal-aware floorplanning is an effective way to solve the thermal problem in modern integrated circuit (IC) designs. Existing thermal-aware floorplanning methods are all based on simulated annealing (SA), genetic algorithms (GAs) or linear programming (LP), which are quite time-consuming. In this paper, we propose two fast algorithms for thermal-aware floorplanning, a greedy algorithm based on the less-flexibility-first (LFF) principle and a hybrid algorithm combining the greedy algorithm and an SA-based refinement. The greedy algorithm can fast obtain a locally optimized floorplan with reduced area and temperature. The hybrid method can get similar results compared with pure SA-based approaches but it is still much faster.

APA, Harvard, Vancouver, ISO, and other styles

9

Wayahdi, Muhammad Rhifky, Subhan Hafiz Nanda Ginting, and Dinur Syahputra. "Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path." International Journal of Advances in Data and Information Systems 2, no. 1 (February 1, 2021): 45–52. http://dx.doi.org/10.25008/ijadis.v2i1.1206.

Full text

Abstract:

The problem of finding the shortest path from a path or graph has been quite widely discussed. There are also many algorithms that are the solution to this problem. The purpose of this study is to analyze the Greedy, A-Star, and Dijkstra algorithms in the process of finding the shortest path. The author wants to compare the effectiveness of the three algorithms in the process of finding the shortest path in a path or graph. From the results of the research conducted, the author can conclude that the Greedy, A-Star, and Dijkstra algorithms can be a solution in determining the shortest path in a path or graph with different results. The Greedy algorithm is fast in finding solutions but tends not to find the optimal solution. While the A-Star algorithm tends to be better than the Greedy algorithm, but the path or graph must have complex data. Meanwhile, Dijkstra's algorithm in this case is better than the other two algorithms because it always gets optimal results.

APA, Harvard, Vancouver, ISO, and other styles

10

Li, Jonathan, Rohan Potru, and Farhad Shahrokhi. "A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph." Algorithms 13, no. 12 (December 14, 2020): 339. http://dx.doi.org/10.3390/a13120339.

Full text

Abstract:

We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm, the recent Linear programming (LP) rounding algorithms and a hybrid algorithm that we design by combining the greedy and LP rounding algorithms. Over the range of test data, all algorithms perform better than anticipated in theory, and have small performance ratios, measured as the size of output divided by the LP objective lower bound. However, each have advantages over the others. For instance, LP rounding algorithm normally outperforms the other algorithms on sparse real-world graphs. On a graph with 400,000+ vertices, LP rounding took less than 15 s of CPU time to generate a solution with performance ratio 1.011, while the greedy and hybrid algorithms generated solutions of performance ratio 1.12 in similar time. For synthetic graphs, the hybrid algorithm normally outperforms the others, whereas for hypercubes and k-Queens graphs, greedy outperforms the rest. Another advantage of the hybrid algorithm is to solve very large problems that are suitable for application of LP rounding (sparse graphs) but LP formulations become formidable in practice and LP solvers crash, as we observed on a real-world graph with 7.7 million+ vertices and a planar graph on 1,000,000 vertices.

APA, Harvard, Vancouver, ISO, and other styles

11

Livshits, E. D. "Realizability of greedy algorithms." Proceedings of the Steklov Institute of Mathematics 273, S1 (June 18, 2011): 107–15. http://dx.doi.org/10.1134/s0081543811050117.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Sancetta, Alessio. "Greedy algorithms for prediction." Bernoulli 22, no. 2 (May 2016): 1227–77. http://dx.doi.org/10.3150/14-bej691.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Sundman, Dennis, Saikat Chatterjee, and Mikael Skoglund. "Distributed greedy pursuit algorithms." Signal Processing 105 (December 2014): 298–315. http://dx.doi.org/10.1016/j.sigpro.2014.05.027.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Dickerson, Matthew T., Robert L. Scot Drysdale, Scott A. McElfresh, and Emo Welzl. "Fast greedy triangulation algorithms." Computational Geometry 8, no. 2 (July 1997): 67–86. http://dx.doi.org/10.1016/s0925-7721(97)89149-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

GRECO, SERGIO, and CARLO ZANIOLO. "Greedy algorithms in Datalog." Theory and Practice of Logic Programming 1, no. 4 (June 25, 2001): 381–407. http://dx.doi.org/10.1017/s1471068401001090.

Full text

Abstract:

In the design of algorithms, the greedy paradigm provides a powerful tool for solving efficiently classical computational problems, within the framework of procedural languages. However, expressing these algorithms within the declarative framework of logic-based languages has proven a difficult research challenge. In this paper, we extend the framework of Datalog-like languages to obtain simple declarative formulations for such problems, and propose effective implementation techniques to ensure computational complexities comparable to those of procedural formulations. These advances are achieved through the use of the choice construct, extended with preference annotations to effect the selection of alternative stable-models and nondeterministic fixpoints. We show that, with suitable storage structures, the differential fixpoint computation of our programs matches the complexity of procedural algorithms in classical search and optimization problems.

APA, Harvard, Vancouver, ISO, and other styles

16

Liu, Entao, and Vladimir N. Temlyakov. "Super greedy type algorithms." Advances in Computational Mathematics 37, no. 4 (September 30, 2011): 493–504. http://dx.doi.org/10.1007/s10444-011-9220-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Haider, Syed Aqib. "Matroids And Greedy Algorithms. A Deeper Justification of Using Greedy Approach To Find A Maximal set of a Matroid." Annales Universitatis Mariae Curie-Sklodowska, sectio AI – Informatica 16, no. 2 (December 22, 2017): 48. http://dx.doi.org/10.17951/ai.2016.16.2.48.

Full text

Abstract:

<p>Greedy algorithms are used in solving a diverse set of problems in small computation time. However, for solving problems using greedy approach, it must be proved that the greedy strategy applies. The greedy approach relies on selection of optimal choice at a local level reducing the problem to a single sub problem, which actually leads to a globally optimal solution. Finding a maximal set from the independent set of a matroid M(S, I) also uses greedy approach and justification is also provided in standard literature (e.g. Introduction to Algorithms by Cormen et .al.). However, the justification does not clearly explain the equivalence of using greedy algorithm and contraction of M by the selected element. This paper thus attempts to give a lucid explanation of the fact that the greedy algorithm is equivalent to reducing the Matroid into its contraction by selected element. This approach also provides motivation for research on the selection of the test used in algorithm which might lead to smaller computation time of the algorithm.</p>

APA, Harvard, Vancouver, ISO, and other styles

18

Liang, Rui Hua, Xin Peng Du, Qing Bo Zhao, and Li Zhi Cheng. "Sparse Signal Recovery Based on Simulated Annealing." Applied Mechanics and Materials 321-324 (June 2013): 1295–98. http://dx.doi.org/10.4028/www.scientific.net/amm.321-324.1295.

Full text

Abstract:

Sparse signal recovery is a hot topic in the fields of optimization theory and signal processing. Two main algorithmic approaches, i.e. greedy pursuit algorithms and convex relaxation algorithms have been extensively used to solve this problem. However, these algorithms cannot guarantee to find the global optimum solution, and then they perform poorly when the sparsity level is relatively large. Based on the simulated annealing algorithm and greedy pursuit algorithms, we propose a novel algorithm on solving the sparse recovery problem. Numerical simulations show that the proposed algorithm has very good recovery performance.

APA, Harvard, Vancouver, ISO, and other styles

19

Ababneh, Jehad. "Greedy particle swarm and biogeography-based optimization algorithm." International Journal of Intelligent Computing and Cybernetics 8, no. 1 (March 9, 2015): 28–49. http://dx.doi.org/10.1108/ijicc-01-2014-0003.

Full text

Abstract:

Purpose – The purpose of this paper is to propose an algorithm that combines the particle swarm optimization (PSO) with the biogeography-based optimization (BBO) algorithm. Design/methodology/approach – The BBO and the PSO algorithms are jointly used in to order to combine the advantages of both algorithms. The efficiency of the proposed algorithm is tested using some selected standard benchmark functions. The performance of the proposed algorithm is compared with that of the differential evolutionary (DE), genetic algorithm (GA), PSO, BBO, blended BBO and hybrid BBO-DE algorithms. Findings – Experimental results indicate that the proposed algorithm outperforms the BBO, PSO, DE, GA, and the blended BBO algorithms and has comparable performance to that of the hybrid BBO-DE algorithm. However, the proposed algorithm is simpler than the BBO-DE algorithm since the PSO does not have complex operations such as mutation and crossover used in the DE algorithm. Originality/value – The proposed algorithm is a generic algorithm that can be used to efficiently solve optimization problems similar to that solved using other popular evolutionary algorithms but with better performance.

APA, Harvard, Vancouver, ISO, and other styles

20

Selvi, V. "Clustering Analysis of Greedy Heuristic Method in Zero_One Knapsack Problem." International Journal of Emerging Research in Management and Technology 6, no. 7 (June 29, 2018): 39. http://dx.doi.org/10.23956/ijermt.v6i7.181.

Full text

Abstract:

Knapsack problem is a surely understood class of optimization problems, which tries to expand the profit of items in a knapsack without surpassing its capacity, Knapsack can be solved by several algorithms such like Greedy, dynamic programming, Branch & bound etc. The solution to the zero_one knapsack problem (KP) can be viewed as the result of a sequence of decision. Clustering is the process of resolving that type of applications. Different clustering application for grouping elements with equal priority. In this paper we are introducing greedy heuristic algorithm for solving zero_one knapsack problem. We will exhibit a relative investigation of the Greedy, dynamic programming, B&B and Genetic algorithms regarding of the complexity of time requirements, and the required programming efforts and compare the total value for each of them. Greedy and Genetic algorithms can be used to solve the 0-1 Knapsack problem within a reasonable time complexity. The worst-case time complexity (Big-O) of both algorithms is O(N). Using the greedy method, the algorithm can produce high quality clusters while reduce time the best partioning avoid the memory confinement problem during the process.

APA, Harvard, Vancouver, ISO, and other styles

21

Zhao, Hongtu, Chong Chen, and Chenxu Shi. "Image reconstruction algorithm based on variable atomic number matching pursuit." Journal of Algorithms & Computational Technology 11, no. 2 (October 12, 2016): 103–9. http://dx.doi.org/10.1177/1748301816673074.

Full text

Abstract:

As the most critical part of compressive sensing theory, reconstruction algorithm has an impact on the quality and speed of image reconstruction. After studying some existing convex optimization algorithms and greedy algorithms, we find that convex optimization algorithms should possess higher complexity to achieve higher reconstruction quality. Also, fixed atomic numbers used in most greedy algorithms increase the complexity of reconstruction. In this context, we propose a novel algorithm, called variable atomic number matching pursuit, which can improve the accuracy and speed of reconstruction. Simulation results show that variable atomic number matching pursuit is a fast and stable reconstruction algorithm and better than the other reconstruction algorithms under the same conditions.

APA, Harvard, Vancouver, ISO, and other styles

22

Liu, Wenhui, Da Gong, and Zhiqiang Xu. "One-Bit Compressed Sensing by Greedy Algorithms." Numerical Mathematics: Theory, Methods and Applications 9, no. 2 (May 2016): 169–84. http://dx.doi.org/10.4208/nmtma.2016.m1428.

Full text

Abstract:

AbstractSign truncated matching pursuit (STrMP) algorithm is presented in this paper. STrMP is a new greedy algorithm for the recovery of sparse signals from the sign measurement, which combines the principle of consistent reconstruction with orthogonal matching pursuit (OMP). The main part of STrMP is as concise as OMP and hence STrMP is simple to implement. In contrast to previous greedy algorithms for one-bit compressed sensing, STrMP only need to solve a convex and unconstrained subproblem at each iteration. Numerical experiments show that STrMP is fast and accurate for one-bit compressed sensing compared with other algorithms.

APA, Harvard, Vancouver, ISO, and other styles

23

Perea, Federico, and Huub W. De Waard. "Greedy and $K$-Greedy Algorithms for Multidimensional Data Association." IEEE Transactions on Aerospace and Electronic Systems 47, no. 3 (July 2011): 1915–25. http://dx.doi.org/10.1109/taes.2011.5937273.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Temlyakov, V. N. "Greedy approximation." Acta Numerica 17 (April 25, 2008): 235–409. http://dx.doi.org/10.1017/s0962492906380014.

Full text

Abstract:

In this survey we discuss properties of specific methods of approximation that belong to a family of greedy approximation methods (greedy algorithms). It is now well understood that we need to study nonlinear sparse representations in order to significantly increase our ability to process (compress, denoise,etc.) large data sets. Sparse representations of a function are not only a powerful analytic tool but they are utilized in many application areas such as image/signal processing and numerical computation. The key to finding sparse representations is the concept ofm-term approximation of the target function by the elements of a given system of functions (dictionary). The fundamental question is how to construct good methods (algorithms) of approximation. Recent results have established that greedy-type algorithms are suitable methods of nonlinear approximation in bothm-term approximation with regard to bases, andm-term approximation with regard to redundant systems. It turns out that there is one fundamental principle that allows us to build good algorithms, both for arbitrary redundant systems and for very simple well-structured bases, such as the Haar basis. This principle is the use of a greedy step in searching for a new element to be added to a givenm-term approximant.

APA, Harvard, Vancouver, ISO, and other styles

25

Galatenko, V. V., and E. D. Livshits. "Generalized Approximate Weak Greedy Algorithms." Mathematical Notes 78, no. 1-2 (July 2005): 170–84. http://dx.doi.org/10.1007/s11006-005-0113-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Duxbury, P. M., and R. Dobrin. "Greedy algorithms in disordered systems." Physica A: Statistical Mechanics and its Applications 270, no. 1-2 (August 1999): 263–69. http://dx.doi.org/10.1016/s0378-4371(99)00132-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Nguyen, Thanh Thi, Jerome Idier, Charles Soussen, and El-Hadi Djermoune. "Non-Negative Orthogonal Greedy Algorithms." IEEE Transactions on Signal Processing 67, no. 21 (November 1, 2019): 5643–58. http://dx.doi.org/10.1109/tsp.2019.2943225.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Schnass, K., and P. Vandergheynst. "Dictionary Preconditioning for Greedy Algorithms." IEEE Transactions on Signal Processing 56, no. 5 (May 2008): 1994–2002. http://dx.doi.org/10.1109/tsp.2007.911494.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Curtis, S. A. "The classification of greedy algorithms." Science of Computer Programming 49, no. 1-3 (December 2003): 125–57. http://dx.doi.org/10.1016/j.scico.2003.09.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Moran, José, and Jean-Philippe Bouchaud. "Greedy algorithms and Zipf laws." Journal of Statistical Mechanics: Theory and Experiment 2018, no. 4 (April 9, 2018): 043402. http://dx.doi.org/10.1088/1742-5468/aab50a.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Bird, R. S. "Functional Pearls Two greedy algorithms." Journal of Functional Programming 2, no. 2 (April 1992): 237–44. http://dx.doi.org/10.1017/s0956796800000368.

Full text

Abstract:

At the recent TC2 working conference on constructing programs from specifications (Moeller, 1991), I presented the derivation of a functional program for solving a problem posed by Knuth (1990). Slightly simplified, the problem was to construct a shortest decimal fraction representing a given integer multiple of 1/216. Later in the conference – and in a different context – Robert Dewar described a second problem that he had recently set as an examination question. In brief, the problem was to replace sequences of blanks in a file by tab characters wherever possible. Although Knuth's and Dewar's problems appear to have little in common, I suspected that both had the same ‘deep structure’ and were instances of a single general result about greedy algorithms. The purpose of this note is to bring the genral result to light and to unify the treatment of the two problems. We begin by describing the problems more precisely.

APA, Harvard, Vancouver, ISO, and other styles

32

Bird, Richard S. "Functional Pearls: Unravelling greedy algorithms." Journal of Functional Programming 2, no. 3 (July 1992): 375–85. http://dx.doi.org/10.1017/s0956796800000459.

Full text

Abstract:

In my previous Functional Pearls article (Bird, 1992), I proved a theorem giving conditions under which an optimization problem could be implemented by a greedy algorithm. A greedy algorithm is one that picks a ‘best’ element at each stage. Here, we return to this theorem and extend it in various ways. We then use the theory to solve an intriguing problem about unravelling sequences into a smallest number of ascending subsequences.

APA, Harvard, Vancouver, ISO, and other styles

33

Ferrari, Luca. "Greedy algorithms and poset matroids." Journal of Discrete Algorithms 29 (November 2014): 21–26. http://dx.doi.org/10.1016/j.jda.2014.07.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Contucci, Pierluigi, Cristian Giardinà, Claudio Giberti, Francesco Unguendoli, and Cecilia Vernia. "Interpolating greedy and reluctant algorithms." Optimization Methods and Software 20, no. 4-5 (August 2005): 509–14. http://dx.doi.org/10.1080/10556780500140177.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Levcopoulos, Christos, and Andrzej Lingas. "Fast algorithms for greedy triangulation." BIT 32, no. 2 (June 1992): 280–96. http://dx.doi.org/10.1007/bf01994882.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

DeVore, R. A., and V. N. Temlyakov. "Some remarks on greedy algorithms." Advances in Computational Mathematics 5, no. 1 (December 1996): 173–87. http://dx.doi.org/10.1007/bf02124742.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Temlyakov, Vladimir. "Greedy Algorithms with Prescribed Coefficients." Journal of Fourier Analysis and Applications 13, no. 1 (February 2007): 71–86. http://dx.doi.org/10.1007/s00041-006-6033-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Zhang, Huaming, and Xiang-Zhi Kong. "On k-greedy routing algorithms." Computational Geometry 52 (February 2016): 9–17. http://dx.doi.org/10.1016/j.comgeo.2015.10.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Temlyakov, Vladimir N., and Pavel Zheltov. "On performance of greedy algorithms." Journal of Approximation Theory 163, no. 9 (September 2011): 1134–45. http://dx.doi.org/10.1016/j.jat.2011.03.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Leviatan, D., and V. N. Temlyakov. "Simultaneous approximation by greedy algorithms." Advances in Computational Mathematics 25, no. 1-3 (July 2006): 73–90. http://dx.doi.org/10.1007/s10444-004-7613-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Li, Xu Hua, Yue Li Chen, Nan Jun Hu, Wei Li, Tian Jun Yuan, Yu Wang, and Ying Hou. "Signal Reconstruction Based on a Fusion Compressed Sensing Frame." Advanced Materials Research 785-786 (September 2013): 1315–23. http://dx.doi.org/10.4028/www.scientific.net/amr.785-786.1315.

Full text

Abstract:

Greedy algorithms represented by orthogonal matching pursuit (OMP) and subspace pursuit (SP) algorithms are practically used in image processing based upon compressed sensing theory. However, there are two disadvantages: 1)Relatively poor signal reconstruction accuracy; 2) High computation complexity and measurements time. This paper proposes a frame of greedy algorithms obtaining a novel fusion of matching pursuit (FMP), combining the OMP and SP algorithms. FMP unites the two support sets from OMP and SP selecting the most appropriate atoms to achieve secondary screening of the original two support sets, finally realizing the accurate signal reconstruction. Using same test conditions, image reconstruction experiments and stability of Frame, the proposed FMP algorithm can effectively improve signal-to-noise ratio (SNR) with improved reconstruction error. Reconstruction effects using proposed FMP are better than separately using other two greedy algorithms for both high and low resolution images.

APA, Harvard, Vancouver, ISO, and other styles

42

Gupta, Varun, Benjamin Moseley, Marc Uetz, and Qiaomin Xie. "Corrigendum: Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling." Mathematics of Operations Research 46, no. 3 (August 2021): 1230–34. http://dx.doi.org/10.1287/moor.2021.1149.

Full text

Abstract:

This corrigendum fixes an incorrect claim in the paper Gupta et al. [Gupta V, Moseley B, Uetz M, Xie Q (2020) Greed works—online algorithms for unrelated machine stochastic scheduling. Math. Oper. Res. 45(2):497–516.], which led us to claim a performance guarantee of 6 for a greedy algorithm for deterministic online scheduling with release times on unrelated machines. The result is based on an upper bound on the increase of the objective function value when adding an additional job [Formula: see text] to a machine [Formula: see text] (Gupta et al., lemma 6). It was pointed out by Sven Jäger from Technische Universität Berlin that this upper bound may fail to hold. We here present a modified greedy algorithm and analysis, which leads to a performance guarantee of 7.216 instead. Correspondingly, also the claimed performance guarantee of [Formula: see text] in theorem 4 of Gupta et al. for the stochastic online problem has to be corrected. We obtain a performance bound [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

43

Hulianytskyi, Leonid, and Sergii Chornozhuk. "Genetic Algorithm with New Stochastic Greedy Crossover Operator for Protein Structure Folding Problem." Cybernetics and Computer Technologies, no. 2 (July 24, 2020): 19–29. http://dx.doi.org/10.34229/2707-451x.20.2.3.

Full text

Abstract:

Introduction. The spatial protein structure folding is an important and actual problem in biology. Considering the mathematical model of the task, we can conclude that it comes down to the combinatorial optimization problem. Therefore, genetic and mimetic algorithms can be used to find a solution. The article proposes a genetic algorithm with a new greedy stochastic crossover operator, which differs from classical approaches with paying attention to qualities of possible ancestors. The purpose of the article is to describe a genetic algorithm with a new greedy stochastic crossover operator, reveal its advantages and disadvantages, compare the proposed algorithm with the best-known implementations of genetic and memetic algorithms for the spatial protein structure prediction, and make conclusions with future steps suggestion afterward. Result. The work of the proposed algorithm is compared with others on the basis of 10 known chains with a length of 48 first proposed in [13]. For each of the chain, a global minimum of free energy was already precalculated. The algorithm found 9 out of 10 spatial structures on which a global minimum of free energy is achieved and also demonstrated a better average value of solutions than the comparing algorithms. Conclusion. The quality of the genetic algorithm with the greedy stochastic crossover operator has been experimentally confirmed. Consequently, its further research is promising. For example, research on the selection of optimal algorithm parameters, improving the speed and quality of solutions found through alternative coding or parallelization. Also, it is worth testing the proposed algorithm on datasets with proteins of other lengths for further checks of the algorithm’s validity. Keywords: spatial protein structure, combinatorial optimization, genetic algorithms, crossover operator, stochasticity.

APA, Harvard, Vancouver, ISO, and other styles

44

Lopateeva, Olga, Anatoly Popov, Alexey Ovsyankin, and Mikhail Satsuk. "Formation of the schedule at the university with the application of greedy algorithms." Informatization and communication 4 (November 2020): 91–96. http://dx.doi.org/10.34219/2078-8320-2020-11-4-91-96.

Full text

Abstract:

A greedy resource allocation algorithm is understood as an algorithm according to which the resource allocation process can be represented as a sequence of steps. At each step, an optimal, under certain conditions, distribution of a part of the resources occurs, which does not change in the future. The problem of improving the quality of the organization of the educational process in a higher educational institution is solved on the basis of the use of greedy algorithms. A well-designed timetable should ensure an even workload of student groups and faculty. The purpose of this work is to develop an algorithm that can improve the quality of the formation of the educational schedule based on the use of greedy algorithms.

APA, Harvard, Vancouver, ISO, and other styles

45

Jing, Xiaoqian, and Haihe Shi. "A New Implementation of Genome Rearrangement Problem." Journal of Healthcare Engineering 2021 (January 23, 2021): 1–9. http://dx.doi.org/10.1155/2021/6692775.

Full text

Abstract:

Unsigned reverse genome rearrangement is an important part of bioinformatics research, which is widely used in biological similarity and homology analysis, revealing biological inheritance, variation, and evolution. Branch and bound, simulated annealing, and other algorithms in unsigned reverse genome rearrangement algorithm are rare in practical application because of their huge time and space consumption, and greedy algorithms are mostly used at present. By deeply analyzing the domain of unsigned reverse genome rearrangement algorithm based on greedy strategy (unsigned reverse genome rearrangement algorithm (URGRA) based on greedy strategy), the domain features are modeled, and the URGRA algorithm components are interactively designed according to the production programming method. With the support of the PAR platform, the algorithm component library of the URGRA is formally realized, and the concrete algorithm is generated by assembly, which improves the reliability of the assembly algorithm.

APA, Harvard, Vancouver, ISO, and other styles

46

Kazakovtsev, Lev, Dmitry Stashkov, Mikhail Gudyma, and Vladimir Kazakovtsev. "Algorithms with greedy heuristic procedures for mixture probability distribution separation." Yugoslav Journal of Operations Research 29, no. 1 (2019): 51–67. http://dx.doi.org/10.2298/yjor171107030k.

Full text

Abstract:

For clustering problems based on the model of mixture probability distribution separation, we propose new Variable Neighbourhood Search algorithms (VNS) and evolutionary genetic algorithms (GA) with greedy agglomerative heuristic procedures and compare them with known algorithms. New genetic algorithms implement a global search strategy with the use of a special crossover operator based on greedy agglomerative heuristic procedures in combination with the EM algorithm (Expectation Maximization). In our new VNS algorithms, this combination is used for forming randomized neighbourhoods to search for better solutions. The results of computational experiments made on classical data sets and the testings of production batches of semiconductor devices shipped for the space industry demonstrate that new algorithms allow us to obtain better results, higher values of the log likelihood objective function, in comparison with the EM algorithm and its modifications.

APA, Harvard, Vancouver, ISO, and other styles

47

Xie, Jun, Yu (Marco) Nie, and Xiaobo Liu. "A Greedy Path-Based Algorithm for Traffic Assignment." Transportation Research Record: Journal of the Transportation Research Board 2672, no. 48 (May 24, 2018): 36–44. http://dx.doi.org/10.1177/0361198118774236.

Full text

Abstract:

This paper presents a new path-based algorithm for the static user equilibrium traffic assignment problem. Path-based algorithms are generally considered less efficient than bush-based counterparts, such as Algorithm B, traffic assignment by paired alternative segments (TAPAS), and iTAPAS, an improved version of TAPAS, because explicitly storing and manipulating paths appears wasteful. However, our numerical experiments indicate that the proposed path-based algorithm can outperform TAPAS or iTAPAS by a wide margin. The proposed algorithm, sharing the same Gauss-Seidel decomposition scheme with existing path-based algorithms, delivered a surprising performance, most likely due to its two main features. First, it adopts a greedy method to solve the restricted subproblem defined on each origin–destination (O-D) pair. Second, instead of sequentially visiting every O-D pair in each iteration, it introduces an intelligent scheme to determine which O-D pairs need more or less work. The proposed algorithm is also more straightforward to implement than bush-based algorithms.

APA, Harvard, Vancouver, ISO, and other styles

48

Chen, Wei, Binghui Peng, Grant Schoenebeck, and Biaoshuai Tao. "Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 01 (April 3, 2020): 590–97. http://dx.doi.org/10.1609/aaai.v34i01.5398.

Full text

Abstract:

We consider the adaptive influence maximization problem: given a network and a budget k, iteratively select k seeds in the network to maximize the expected number of adopters. In the full-adoption feedback model, after selecting each seed, the seed-picker observes all the resulting adoptions. In the myopic feedback model, the seed-picker only observes whether each neighbor of the chosen seed adopts. Motivated by the extreme success of greedy-based algorithms/heuristics for influence maximization, we propose the concept of greedy adaptivity gap, which compares the performance of the adaptive greedy algorithm to its non-adaptive counterpart. Our first result shows that, for submodular influence maximization, the adaptive greedy algorithm can perform up to a (1-1/e)-fraction worse than the non-adaptive greedy algorithm, and that this ratio is tight. More specifically, on one side we provide examples where the performance of the adaptive greedy algorithm is only a (1-1/e) fraction of the performance of the non-adaptive greedy algorithm in four settings: for both feedback models and both the independent cascade model and the linear threshold model. On the other side, we prove that in any submodular cascade, the adaptive greedy algorithm always outputs a (1-1/e)-approximation to the expected number of adoptions in the optimal non-adaptive seed choice. Our second result shows that, for the general submodular cascade model with full-adoption feedback, the adaptive greedy algorithm can outperform the non-adaptive greedy algorithm by an unbounded factor. Finally, we propose a risk-free variant of the adaptive greedy algorithm that always performs no worse than the non-adaptive greedy algorithm.

APA, Harvard, Vancouver, ISO, and other styles

49

Hammond, Joshua E., Cory A. Vernon, Trent J. Okeson, Benjamin J. Barrett, Samuel Arce, Valerie Newell, Joseph Janson, Kevin W. Franke, and John D. Hedengren. "Survey of 8 UAV Set-Covering Algorithms for Terrain Photogrammetry." Remote Sensing 12, no. 14 (July 16, 2020): 2285. http://dx.doi.org/10.3390/rs12142285.

Full text

Abstract:

Remote sensing with unmanned aerial vehicles (UAVs) facilitates photogrammetry for environmental and infrastructural monitoring. Models are created with less computational cost by reducing the number of photos required. Optimal camera locations for reducing the number of photos needed for structure-from-motion (SfM) are determined through eight mathematical set-covering algorithms as constrained by solve time. The algorithms examined are: traditional greedy, reverse greedy, carousel greedy (CG), linear programming, particle swarm optimization, simulated annealing, genetic, and ant colony optimization. Coverage and solve time are investigated for these algorithms. CG is the best method for choosing optimal camera locations as it balances number of photos required and time required to calculate camera positions as shown through an analysis similar to a Pareto Front. CG obtains a statistically significant 3.2 fewer cameras per modeled area than base greedy algorithm while requiring just one additional order of magnitude of solve time. For comparison, linear programming is capable of fewer cameras than base greedy but takes at least three orders of magnitude longer to solve. A grid independence study serves as a sensitivity analysis of the CG algorithms α (iteration number) and β (percentage to be recalculated) parameters that adjust traditional greedy heuristics, and a case study at the Rock Canyon collection dike in Provo, UT, USA, compares the results of all eight algorithms and the uniqueness (in terms of percentage comparisons based on location/angle metadata and qualitative visual comparison) of each selected set. Though this specific study uses SfM, the principles could apply to other instruments such as multi-spectral cameras or aerial LiDAR.

APA, Harvard, Vancouver, ISO, and other styles

50

Goyal, Shashank, and Diwakar Gupta. "The Online Reservation Problem." Algorithms 13, no. 10 (September 23, 2020): 241. http://dx.doi.org/10.3390/a13100241.

Full text

Abstract:

Many sharing-economy platforms operate as follows. Owners list the availability of resources, prices, and contract-length limits. Customers propose contract start times and lengths. The owners decide immediately whether to accept or decline each proposal, even if the contract is for a future date. Accepted proposals generate revenue. Declined proposals are lost. At any decision epoch, the owner has no information regarding future proposals. The owner seeks easy-to-implement algorithms that achieve the best competitive ratio (CR). We first derive a lower bound on the CR of any algorithm. We then analyze CRs of all intuitive “greedy” algorithms. We propose two new algorithms that have significantly better CRs than that of any greedy algorithm for certain parameter-value ranges. The key idea behind these algorithms is that owners may reserve some amount of capacity for late-arriving higher-value proposals in an attempt to improve revenue. Our contribution lies in operationalizing this idea with the help of algorithms that utilize thresholds. Moreover, we show that if non-optimal thresholds are chosen, then those may lead to poor CRs. We provide a rigorous method by which an owner can decide the best approach in their context by analyzing the CRs of greedy algorithms and those proposed by us.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!