Spelling suggestions: "subject:"greedy algorithm"" "subject:"creedy algorithm""
1 
Atomic structure and mechanical properties of of BC2NHuang, ZhiQuan 06 July 2010 (has links)
Structural motifs for the BC2N superlattices were identified from a systematic search based on a greedy algorithm. Using a tree data structure, we have retrieved seven structural models for cBC2N 1x1x lattice which were identified previously by Sun et al. [Phys. Rev. B 64, 094108 (2001)]. Furthermore, the atomic structures with the maximum number of CC bonds for cBC2N 2x2x2, 3x3x3, and 4x4x4 superlattices were found by imposing the greedy algorithm in the tree data structure. This new structural motif has not been previously proposed in the literature. A total of up to 512 atoms in the cBC2N superlattice are taken into consideration. The atoms in these superlattices are in diamondlike structural form. Furthermore, the C atoms, as well as B and N atoms, form the octahedral motif separately. The octahedral structure consisting of C is bounded with {111} facets, and each facet is interfaced to a neighboring octahedral structure consisting of B and N atoms. The electronic and mechanical properties of newly identified low energy structures were analyzed.

2 
Optimal Allocation of Satellite Network ResourcesBurrowbridge, Sarah Elizabeth 31 December 1999 (has links)
This work examines a straightforward solution to a problem of satellite network resource allocation by exploring the application of an optimal algorithm to a subset of the general scheduling problem. Making some basic simplifications, such as the limitation of the mission scenarios to Low Earth Orbiting satellites, allows the effective application of the rigorous methods of the Greedy ActivitySelector algorithm. Tools such as Analytical Graphic's Satellite Tool Kit and MATLAB 5.0 are integrated to assist in the implementation of the algorithm. Several examples are presented in order to illustrate the effectiveness of the process. / Master of Science

3 
Analysis of Algorithms for Combinatorial Auctions and Related ProblemsGhebreamlak, Kidane Asrat January 2005 (has links)
The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multiunit combinatorial auction. In the second paper, we compare the revenues from a secondprice combinatorial auction against a secondprice oneshot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the oneshot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are riskaverse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter. The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3set packing on a weighted hypergraph, and hence NPcomplete. However, the greedy algorithm approximates this special case within a factor of 3. In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices. In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2dimensional Gaussian process as M goes to infinity.

4 
Spanning Tree Approach On The Snow Cleaning ProblemHossain, Mohammad Forhad January 2010 (has links)
Snow cleaning is one of the important tasks in the winter time in Sweden. Every year government spends huge amount money for snow cleaning purpose. In this thesis we generate a shortest road network of the city and put the depots in different place of the city for snow cleaning. We generate shortest road network using minimum spanning tree algorithm and find the depots position using greedy heuristic. When snow is falling, vehicles start work from the depots and clean the snow all the road network of the city. We generate two types of model. Models are economic model and efficient model. Economic model provide good economical solution of the problem and it use less number of vehicles. Efficient model generate good efficient solution and it take less amount of time to clean the entire road network.

5 
Survey of Approximation Algorithms for Set Cover ProblemDutta, Himanshu Shekhar 12 1900 (has links)
In this thesis, I survey 11 approximation algorithms for unweighted set cover problem. I have also implemented the three algorithms and created a software library that stores the code I have written. The algorithms I survey are: 1. Johnson's standard greedy; 2. ffrequency greedy; 3. Goldsmidt, Hochbaum and Yu's modified greedy; 4. Halldorsson's local optimization; 5. Dur and Furer semi local optimization; 6. Asaf Levin's improvement to Dur and Furer; 7. Simple rounding; 8. Randomized rounding; 9. LP duality; 10. Primaldual schema; and 11. Network flow technique. Most of the algorithms surveyed are refinements of standard greedy algorithm.

6 
Spanning tree modulus: deflation and a hierarchical graph structureClemens, Jason January 1900 (has links)
Doctor of Philosophy / Department of Mathematics / Nathan Albin / The concept of discrete $p$modulus provides a general framework for understanding arbitrary families of objects on a graph. The $p$modulus provides a sense of ``structure'' of the underlying graph, with different families of objects leading to different insight into the graph's structure. This dissertation builds on this idea, with an emphasis on the family of spanning trees and the underlying graph structure that spanning tree modulus exposes.
This dissertation provides a review of the probabilistic interpretation of modulus. In the context of spanning trees, this interpretation rephrases modulus as the problem of choosing a probability mass function on the spanning trees so that two independent, identically distributed random spanning trees have expected overlap as small as possible.
A theoretical lower bound on the expected overlap is shown. Graphs that attain this lower bound are called homogeneous and have the property that there exists a probability mass function that gives every edge equal likelihood to appear in a random tree. Moreover, any nonhomogeneous graph necessarily has a homogeneous subgraph (called a homogeneous core), which is shown to split the modulus problem into two smaller subproblems through a process called deflation.
Spanning tree modulus and the process of deflation establish a type of hierarchical structure in the underlying graph that is similar to the concept of coreperiphery structure found in the literature. Using this, one can see an alternative way of decomposing a graph into its hierarchical community components using homogeneous cores and a related concept: minimum feasible partitions.
This dissertation also introduces a simple greedy algorithm for computing the spanning tree modulus that utilizes any efficient algorithm for finding minimum spanning trees. A theoretical proof of the convergence rate is provided, along with computational examples.

7 
Analysis of Algorithms for Combinatorial Auctions and Related ProblemsGhebreamlak, Kidane Asrat January 2005 (has links)
<p>The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multiunit combinatorial auction.</p><p>In the second paper, we compare the revenues from a secondprice combinatorial auction against a secondprice oneshot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the oneshot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are riskaverse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter.</p><p>The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3set packing on a weighted hypergraph, and hence NPcomplete. However, the greedy algorithm approximates this special case within a factor of 3.</p><p>In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices.</p><p>In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2dimensional Gaussian process as M goes to infinity.</p>

8 
Effective Resource Allocation for Noncooperative Spectrum SharingJacobDavid, Dany D. 13 October 2011 (has links)
Spectrum access protocols have been proposed recently to provide flexible and efficient use
of the available bandwidth. Game theory has been applied to the analysis of the problem
to determine the most effective allocation of the users’ power over the bandwidth. However,
prior analysis has focussed on Shannon capacity as the utility function, even though it is
known that real signals do not, in general, meet the Gaussian distribution assumptions of that metric. In a noncooperative spectrum sharing environment, the Shannon capacity utility function results in a waterfilling solution. In this thesis, the suitability of the waterfilling solution is evaluated when using nonGaussian signalling first in a frequency nonselective environment to focus on the resource allocation problem and its outcomes. It is then extended to a frequency selective environment to examine the proposed algorithm in a more realistic wireless environment. It is shown in both scenarios that more effective resource allocation can be achieved when the utility function takes into account the actual signal characteristics.
Further, it is demonstrated that higher rates can be achieved with lower transmitted power,
resulting in a smaller spectral footprint, which allows more efficient use of the spectrum
overall. Finally, future spectrum management is discussed where the waveform adaptation
is examined as an additional option to the wellknown spectrum agility, rate and transmit
power adaptation when performing spectrum sharing.

9 
Characterizing problems for realizing policies in selfadaptive and selfmanaging systemsBalasubramanian, Sowmya 15 March 2013 (has links)
Selfadaptive and selfmanaging systems optimize their own behaviour according to highlevel objectives and constraints. One way for human administrators to effectively specify goals for such optimization problems is using policies. Over the past decade, researchers produced various approaches, models and techniques for policy specification in different areas including distributed systems, communication networks, web services, autonomic computing, and cloud computing. Research challenges range from characterizing policies for ease of specification in particular application domains to categorizing policies for achieving good solution qualities for particular algorithmic techniques.
The contributions of this thesis are threefold. Firstly, we give a mathematical formulation for each of the three policy types, action, goal and utility function policies, introduced in the policy framework by Kephart and Walsh. In particular, we introduce a first precise characterization of goal policies for optimization problems. Secondly, this thesis introduces a mathematical framework that adds structure to the underlying optimization problem for different types of policies. Structure is added either to the objective function or the constraints of the optimization problem. These mathematical structures, imposed on the underlying problem, progressively increase the quality of the solutions obtained when using the greedy optimization technique. Thirdly, we show the applicability of our framework through case studies by analyzing several optimization problems encountered in selfadaptive and selfmanaging systems, such as resource allocation, quality of service management, and Service Level Agreement (SLA) profit optimization to provide quality guarantees for their solutions.
Our approach combines the algorithmic results by Edmonds, Fisher et al., and Mestre, and the policy framework of Kephart and Walsh. Our characterization and approach will help designers of selfadaptive and selfmanaging systems formulate optimization problems, decide on algorithmic strategies based on policy requirements, and reason about solution qualities. / Graduate / 0984

10 
Effective Resource Allocation for Noncooperative Spectrum SharingJacobDavid, Dany D. 13 October 2011 (has links)
Spectrum access protocols have been proposed recently to provide flexible and efficient use
of the available bandwidth. Game theory has been applied to the analysis of the problem
to determine the most effective allocation of the users’ power over the bandwidth. However,
prior analysis has focussed on Shannon capacity as the utility function, even though it is
known that real signals do not, in general, meet the Gaussian distribution assumptions of that metric. In a noncooperative spectrum sharing environment, the Shannon capacity utility function results in a waterfilling solution. In this thesis, the suitability of the waterfilling solution is evaluated when using nonGaussian signalling first in a frequency nonselective environment to focus on the resource allocation problem and its outcomes. It is then extended to a frequency selective environment to examine the proposed algorithm in a more realistic wireless environment. It is shown in both scenarios that more effective resource allocation can be achieved when the utility function takes into account the actual signal characteristics.
Further, it is demonstrated that higher rates can be achieved with lower transmitted power,
resulting in a smaller spectral footprint, which allows more efficient use of the spectrum
overall. Finally, future spectrum management is discussed where the waveform adaptation
is examined as an additional option to the wellknown spectrum agility, rate and transmit
power adaptation when performing spectrum sharing.

Page generated in 0.0819 seconds