133,136 research outputs found
How to make a greedy heuristic for the asymmetric traveling salesman problem competitive
No full textIt is widely confirmed by many computational experiments that a greedy type heuristics for the Traveling Salesman Problem (TSP) produces rather poor solutions except for the Euclidean TSP. The selection of arcs to be included by a greedy heuristic is usually done on the base of cost values. We propose to use upper tolerances of an optimal solution to one of the relaxed Asymmetric TSP (ATSP) to guide the selection of an arc to be included in the final greedy solution. Even though it needs time to calculate tolerances, our computational experiments for the wide range of ATSP instances show that tolerance based greedy heuristics is much more accurate an faster than previously reported greedy type algorithms
Suboptimal greedy power allocation schemes for discrete bit loading
No full textIn this paper we consider low cost discrete bit loading based on greedy power allocation (GPA) under the constraints of total transmit power budget, target BER, and maximum permissible QAM modulation order. Compared to the standard GPA, which is optimal in terms of maximising the data throughput, three suboptimal schemes are proposed, which perform GPA on subsets of subchannels only. These subsets are created by considering the minimum SNR boundaries of QAM levels for a given target BER. We demonstrate how these schemes can significantly reduce the computational complexity required for power allocation, particularly in the case of a large number of subchannels. Two of the proposed algorithms can achieve near optimal performance including a transfer of residual power between subsets at the expense of a very small extra cost. By simulations, we show that the two near optimal schemes, while greatly reducing complexity, perform best in two separate and distinct SNR regions
Greedy power allocation for multicarrier systems with reduced complexity
No full textIn this paper we consider a reduced complexity discrete bit loading for Multicarrier systems based on the greedy power allocation (GPA) under the constraints of transmit power budget, target BER, and maximum permissible QAM modulation order. Compared to the standard GPA, which is optimal in terms of maximising the data throughput, three suboptimal schemes are proposed, which perform GPA on subsets of subcarriers only. These subsets are created by considering the minimum SNR boundaries of QAM levels for a given BER. We demonstrate how these schemes can reduce complexity. Two of the proposed algorithms can achieve near optimal performance by including a transfer of residual power between groups at the expense of a very small extra cost. It is shown that the two near optimal schemes,while greatly reducing complexity, perform best in two separate and distinct SNR regions
Greedy routing and virtual coordinates for future networks
No full textAt the core of the Internet, routers are continuously struggling with
ever-growing routing and forwarding tables. Although hardware advances
do accommodate such a growth, we anticipate new requirements e.g. in
data-oriented networking where each content piece has to be referenced
instead of hosts, such that current approaches relying on global
information will not be viable anymore, no matter the hardware
progress. In this thesis, we investigate greedy routing methods that
can achieve similar routing performance as today but use much less
resources and which rely on local information only. To this end, we
add specially crafted name spaces to the network in which virtual
coordinates represent the addressable entities. Our scheme enables participating
routers to make forwarding decisions using only neighbourhood information,
as the overarching pseudo-geometric name space structure already
organizes and incorporates "vicinity" at a global level.
A first challenge to the application of greedy routing on virtual
coordinates to future networks is that of "routing dead-ends"
that are local minima due to the difficulty of consistent coordinates
attribution. In this context, we propose a routing recovery scheme
based on a multi-resolution embedding of the network in low-dimensional Euclidean spaces.
The recovery is performed by routing greedily on a blurrier view of the network. The
different network detail-levels are obtained though the embedding of
clustering-levels of the graph. When compared with
higher-dimensional embeddings of a given network, our method shows a
significant diminution of routing failures for similar header and
control-state sizes.
A second challenge to the application of virtual coordinates and
greedy routing to future networks is the support of
"customer-provider" as well as "peering" relationships between
participants, resulting in a differentiated services
environment. Although an application of greedy routing within such a
setting would combine two very common fields of today's networking
literature, such a scenario has, surprisingly, not been studied so
far. In this context we propose two approaches to address this scenario.
In a first approach we implement a path-vector protocol similar to
that of BGP on top of a greedy embedding of the network. This allows
each node to build a spatial map associated with each of its
neighbours indicating the accessible regions. Routing is then
performed through the use of a decision-tree classifier taking the
destination coordinates as input. When applied on a real-world dataset
(the CAIDA 2004 AS graph) we demonstrate an up to 40% compression ratio of
the routing control information at the network's core as well as a computationally efficient
decision process comparable to methods such as binary trees and tries.
In a second approach, we take inspiration from consensus-finding in social
sciences and transform the three-dimensional distance data structure
(where the third dimension encodes the service differentiation) into a
two-dimensional matrix on which classical embedding tools can be used.
This transformation is achieved by agreeing on a set of
constraints on the inter-node distances guaranteeing an
administratively-correct greedy routing. The computed distances are
also enhanced to encode multipath support. We demonstrate a good
greedy routing performance as well as an above 90% satisfaction of multipath constraints
when relying on the non-embedded obtained distances on synthetic datasets.
As various embeddings of the consensus distances do not fully exploit their multipath potential, the use of compression techniques such as transform coding to
approximate the obtained distance allows for better routing performances
A new low-cost discrete bit loading using greedy power allocation
No full textIn this paper we consider a low cost bit loading based on the greedy power allocation (GPA). Compared to the standard GPA, which is optimal in terms of maximising the data throughput, three suboptimal schemes are suggested, which perform GPA on subsets of subchannels only. We demonstrate how these schemes can reduce complexity. Two of the proposed algorithms can achieve near optimal performance by including a transfer of residual power between subsets at the expense of a very small extra cost. By simulations, we show that the two near optimal schemes perform best in two separate and distinct SNR regions
Greedy Randomized Adaptive Search and Variable Neighbourhood Search for the minimum labelling spanning tree problem
No full textThis paper studies heuristics for the minimum labelling spanning tree (MLST) problem. The purpose is to find a spanning tree using edges that are as similar as possible. Given an undirected labelled connected graph, the minimum labelling spanning tree problem seeks a spanning tree whose edges have the smallest number of distinct labels. This problem has been shown to be NP-hard. A Greedy Randomized Adaptive Search Procedure (GRASP) and a Variable Neighbourhood Search (VNS) are proposed in this paper. They are compared with other algorithms recommended in the literature: the Modified Genetic Algorithm and the Pilot Method. Nonparametric statistical tests show that the heuristics based on GRASP and VNS outperform the other algorithms tested. Furthermore, a comparison with the results provided by an exact approach shows that we may quickly obtain optimal or near-optimal solutions with the proposed heuristics
Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
No full textWe present an optimal, combinatorial 1−1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm (Calinescu, Chekuri, Pál and Vondrák, 2008), our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by local search. Both phases are run not on the actual objective function, but on a related auxiliary potential function, which is also monotone and submodular. In our previous work on maximum coverage (Filmus and Ward, 2012), the potential function gives more weight to elements covered multiple times. We generalize this approach from coverage functions to arbitrary monotone submodular functions. When the objective function is a coverage function, both definitions of the potential function coincide. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvature c, we adapt our algorithm to produce a (1−e −c)/c approximation. This matches results of Vondrák (2008), who has shown that the continuous greedy algorithm produces a (1 − e −c)/c approximation when the objective function has curvature c with respect to the optimum, and proved that achieving any better approximation ratio is impossible in the value oracle model.
Greedy codes
No full textAbstractGiven an ordered basis of F2n and an integer d, we define a greedy algorithm for constructing a code of minimum distance at least d. We show that these greedy codes are linear and construct a parity check matrix for them. For ordered bases which have a triangular form we are able to give a lower bound on the dimension of greedy codes. Lexicodes are instances of greedy codes. There are examples of greedy codes which are better than lexicodes
The best m-term approximation and greedy algorithms
No full textAbstract. We study nonlinear m-term approximation with regard to a redundant dictionary D in a Hilbert space H. It is known that the Pure Greedy Algorithm (or, more generally, the Weak Greedy Algorithm) provides for each f ∈ H and any dictionary D an expansion into a series f = cj(f)ϕj(f), ϕj(f) ∈ D, j = 1, 2,... j=1 with the Parseval property: �f � 2 = � j |cj(f) | 2. Following the paper of A. Lutoborski and the second author [30] we study analogs of the above expansions for a given finite number of functions f 1,..., f N with a requirement that the dictionary elements ϕj of these expansions are the same for all f i, i = 1,..., N. We study convergence and rate of convergence of such expansions which we call simultaneous expansions. 1
Simultaneous greedy approximation in Banach spaces
No full textAbstractWe study nonlinear m-term approximation with regard to a redundant dictionary D in a Banach space. It is known that in the case of Hilbert space H the pure greedy algorithm (or, more generally, the weak greedy algorithm) provides for each f∈H and any dictionary D an expansion into a seriesf=∑j=1∞cj(f)ϕj(f),ϕj(f)∈D,j=1,2,…with the Parseval property: ∥f∥2=∑j|cj(f)|2. The orthogonal greedy algorithm (or, more generally, the weak orthogonal greedy algorithm) has been introduced in order to enhance the rate of convergence of greedy algorithms. Recently, we have studied analogues of the PGA and WGA for a given finite number of functions f1,…,fN with a requirement that the dictionary elements ϕj of these expansions are the same for all fi, i=1,…,N. We have studied convergence and rate of convergence of such expansions which we call simultaneous expansions. The goal of this paper is twofold. First, we work in a Hilbert space and enhance the convergence of the simultaneous greedy algorithms by introducing an analogue of the orthogonalization process, and we give estimates on the rate of convergence. Then, we study simultaneous greedy approximation in a more general setting, namely, in uniformly smooth Banach spaces
- …
