Search results for "Greedy algorithm."
showing 10 items of 25 documents
PINCoC: a Co-Clustering based Method to Analyze Protein-Protein Interaction Networks
2007
Anovel technique to search for functionalmodules in a protein-protein interaction network is presented. The network is represented by the adjacency matrix associated with the undirected graph modelling it. The algorithm introduces the concept of quality of a sub-matrix of the adjacency matrix, and applies a greedy search technique for finding local optimal solutions made of dense submatrices containing the maximum number of ones. An initial random solution, constituted by a single protein, is evolved to search for a locally optimal solution by adding/removing connected proteins that best contribute to improve the quality function. Experimental evaluations carried out on Saccaromyces Cerevis…
A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems
2005
This paper presents a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional non-guillotine cutting problem, the problem of cutting the rectangular pieces from a large rectangle so as to maximize the value of the pieces cut. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures.
M-GRASP: A GRASP With Memory for Latency-Aware Partitioning Methods in DVE Systems
2009
A necessary condition for providing quality of service to distributed virtual environments (DVEs) is to provide a system response below a maximum threshold to the client computers. In this sense, latency-aware partitioning methods try to provide response times below the threshold to the maximum number of client computers as possible. These partitioning methods should find an assignment of clients to servers that optimizes system throughput, system latency, and partitioning efficiency. In this paper, we present a new algorithm based on greedy randomized adaptive search procedure with memory for finding the best solutions as possible to this problem. We take into account several different alt…
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…
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…
Packing a Trunk
2003
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 × 2 × 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union.
Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
2006
A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infi…
Reactive GRASP for the strip-packing problem
2008
This paper presents a greedy randomized adaptive search procedure (GRASP) for the strip packing problem, which is the problem of placing a set of rectangular pieces into a strip of a given width and infinite height so as to minimize the required height. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances which have been previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures. The results show that the GRASP algorithm outperforms recently reported metaheuristics.
Whom to befriend to influence people
2020
Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person $v$ in the network has a certain threshold $t(v)$ for {\em activation}, i.e adoption of the product or idea. If $v$ has at least $t(v)$ activated neighbors, then $v$ will also become activated. If Alice wants to activate the entire social network, whom should she befriend? More generally, we study the problem of finding the minimum number of links that a set of external influencers should form to people in the network, in order to activate the entire social network. This {\em Minimum Links} Problem has applications in viral marketing and the study of epidemics. Its solution can be…
Boosting Textual Compression in Optimal Linear Time
2005
We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable properties: (a) it can turn any memoryless compressor into a compression algorithm that uses the “best possible” contexts; (b) it is very simple and optimal in terms of time; and (c) it admits a decompression algorithm again optimal in time. To the best of our knowledge, this is the first boosting technique displaying these properties.Technically, our boosting technique builds upon three main ingredients: the Burrows--Wheeler Transform, the Suffix Tree d…