Search results for "greed"
showing 10 items of 57 documents
Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization
2015
We propose several new hybrid heuristics for the differential dispersion problem, the best of which consists of a GRASP with sampled greedy construction with variable neighborhood search for local improvement. The heuristic maintains an elite set of high-quality solutions throughout the search. After a fixed number of GRASP iterations, exterior path relinking is applied between all pairs of elite set solutions and the best solution found is returned. Exterior path relinking, or path separation, a variant of the more common interior path relinking, is first applied in this paper. In interior path relinking, paths in the neighborhood solution space connecting good solutions are explored betwe…
A heuristic for fast convergence in interference-free channel assignment using D1EC coloring
2010
This work proposes an efficient method for solving the Distance-1 Edge Coloring problem (D1EC) for the assignment of orthogonal channels in wireless networks with changing topology. The coloring algorithm is performed by means of the simulated annealing method, a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a suboptimal coloring scheme. Furthermore, a stateful implementation of the D1EC scheme is proposed, in which network coloring is executed upon topology changes. The stateful D1EC is also based on simulated annealing and reduces the algorithm’s convergence time by one order of magnitude in …
On Optimal Solutions for the Optimal Communication Spanning Tree Problem
2009
This paper presents an experimental investigation into the properties of the optimal communication spanning tree (OCST) problem. The OCST problem seeks a spanning tree that connects all the nodes and satisfies their communication requirements at a minimum total cost. The paper compares the properties of random trees to the properties of the best solutions for the OCST problem that are found using an evolutionary algorithm. The results show, on average, that the optimal solution and the minimum spanning tree (MST) share a higher number of links than the optimal solution and a random tree. Furthermore, optimal solutions for OCST problems with randomly chosen distance weights share a higher n…
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…
Randomized heuristics for the Capacitated Clustering Problem
2017
In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these multi-start heuristic search methods when solving this NP-hard problem. The former is a memory-less approach that constructs independent solutions, while the latter is a memory-based method that constructs linked solutions, obtained by partially rebuilding previous ones. Both are based on the combination of greediness and randomization in the constructive process, and coupled with a subsequent l…
Greedy and K-Greedy algoritmhs for multidimensional data association
2011
[EN] The multidimensional assignment (MDA) problem is a combinatorial optimization problem arising in many applications, for instance multitarget tracking (MTT). The objective of an MDA problem of dimension $d\in\Bbb{N}$ is to match groups of $d$ objects in such a way that each measurement is associated with at most one track and each track is associated with at most one measurement from each list, optimizing a certain objective function. It is well known that the MDA problem is NP-hard for $d\geq3$. In this paper five new polynomial time heuristics to solve the MDA problem arising in MTT are presented. They are all based on the semi-greedy approach introduced in earlier research. Experimen…
Optimization of Data Harvesters Deployment in an Urban Areas for an Emergency Scenario
2013
International audience; Since its appearance in the VANETs research community, data collection where vehicles have to explore an area and collect various local data, brings various issues and challenges. Some architectures were proposed to meet data collection requirements. They can be classified into two categories: Decentralized and Centralized self-organizing where different components and techniques are used depending on the application type. In this paper, we treat time-constrained applications in the context of search and rescue missions. For this reason, we propose a centralized architecture where a central unit plans and manages a set of vehicles namely harvesters to get a clear ove…
A Maximal-Space Algorithm for the Container Loading Problem
2008
In this paper, a greedy randomized adaptive search procedure (GRASP) for the container loading problem is presented. This approach is based on a constructive block heuristic that builds upon the concept of maximal space, a nondisjoint representation of the free space in a container. This new algorithm is extensively tested over the complete set of Bischoff and Ratcliff problems [Bischoff, E. E., M. S. W. Ratcliff. 1995. Issues in the development of approaches to container loading. Omega 23 377–390], ranging from weakly heterogeneous to strongly heterogeneous cargo, and outperforms all the known nonparallel approaches that, partially or completely, have used this set of test problems. When …
Ἀνὰ μέσον ἡδονῆςτε καὶ λύπης: Avidità umana e filantropia alla prova dell’oro in Diodoro
2021
In the Third book of his Bibliotheca, Diodorus Siculus includes an account of the Egyptian gold mines and describes the terrible living conditions of the slaves who are exploited to extract the metal. In this regard, Diodorus’ source is the historian Agatharchides of Cnidus, whose account is handed down by the Byzantine writer Photius. The comparison between the two texts allows scholars to highlight the different historical perspective of Diodorus, which privileges a worldview dominated by philanthropy and compassion for the most peripheral humanity. Further confirmation arises from the description of the Iberian mines (V 35-38), which Diodorus derives from the historian and philosopher Po…
Stochastic Learning for SAT- Encoded Graph Coloring Problems
2010
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm’s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.