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 non-cooperative spectrum sharing environment, the Shannon capacity utility function results in a water-filling solution. In this thesis, the suitability of the water-filling solution is evaluated when using non-Gaussian signalling first in a frequency non-selective 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 well-known spectrum agility, rate and transmit power adaptation when performing spectrum sharing.

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 non-cooperative spectrum sharing environment, the Shannon capacity utility function results in a water-filling solution. In this thesis, the suitability of the water-filling solution is evaluated when using non-Gaussian signalling first in a frequency non-selective 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 well-known spectrum agility, rate and transmit power adaptation when performing spectrum sharing.

To connect different electrical, network and data devices with the minimum cost and shortest path, is a complex job. In huge buildings, where the devices are placed at different locations on different floors and only some specific routes are available to pass the cables and buses, the shortest path search becomes more complex. The aim of this thesis project is, to develop an application which indentifies the best path to connect all objects or devices by following the specific routes.To address the above issue we adopted three algorithms Greedy Algorithm, Simulated Annealing and Exhaustive search and analyzed their results. The given problem is similar to Travelling Salesman Problem. Exhaustive search is a best algorithm to solve this problem as it checks each and every possibility and give the accurate result but it is an impractical solution because of huge time consumption. If no. of objects increased from 12 it takes hours to search the shortest path. Simulated annealing is emerged with some promising results with lower time cost. As of probabilistic nature, Simulated annealing could be non optimal but it gives a near optimal solution in a reasonable duration. Greedy algorithm is not a good choice for this problem. So, simulated annealing is proved best algorithm for this problem. The project has been implemented in C-language which takes input and store output in an Excel Workbook

In this thesis, the analysis of the method of fundamental solution(MFS) is expanded for biharmonic equations. The bounds of errors are derived for the traditional and the Almansi's approaches in bounded simply-connected domains. The exponential and the polynomial convergence rates are obtained from highly and finite smooth solutions, respectively. Also the bounds of condition number are derived for the disk domains, to show the exponential growth rates. The analysis in this thesis is the first time to provide the rigor analysis of the CTM for biharmonic equations, and the intrinsic nature of accuracy and stability is similar to that of Laplace's equation. Numerical experiment are carried out for both smooth and singularity problems. The numerical results coincide with the theoretical analysis made. When the particular solutions satisfying the biharmonic equation can be found, the method of particular solutions(MPS) is always superior to MFS, supported by numerical examples. However, if such singular particular solutions near the singular points can not be found, the local refinement of collocation nodes and the greedy adaptive techniques can be used. It seems that the greedy adaptive techniques may provide a better solution for singularity problems. Beside, the numerical solutions by Almansi's approaches are slightly better in accuracy and stability than those by the traditional FS. Hence, the MFS with Almansi's approaches is recommended, due to the simple analysis, which can be obtained directly from the analysis of MFS for Laplace's equation.

Probabilistic graphical models are used in a variety of domains to capture and represent general dependencies in joint probability distributions. In this document we examine the problem of learning the structure of an undirected graphical model, also called a Markov Random Field (MRF), given a set of independent and identically distributed (i.i.d.) samples. Specifically, we introduce an adaptive forward-backward greedy algorithm for learning the structure of a discrete, pairwise MRF given a high dimensional set of i.i.d. samples. The algorithm works by greedily estimating the neighborhood of each node independently through a series of forward and backward steps. By imposing a restricted strong convexity condition on the structure of the learned graph we show that the structure can be fully learned with high probability given $n=\Omega(d\log (p))$ samples where $d$ is the dimension of the graph and $p$ is the number of nodes. This is a significant improvement over existing convex-optimization based algorithms that require a sample complexity of $n=\Omega(d^2\log(p))$ and a stronger irrepresentability condition. We further support these claims with an empirical comparison of the greedy algorithm to node-wise $\ell_1$-regularized logistic regression as well as provide a real data analysis of the greedy algorithm using the Audioscrobbler music listener dataset. The results of this document provide an additional representation of work submitted by A. Jalali, C. Johnson, and P. Ravikumar to NIPS 2011. / text

No description available.

Self-adaptive and self-managing systems optimize their own behaviour according to high-level 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 self-adaptive and self-managing 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 self-adaptive and self-managing systems formulate optimization problems, decide on algorithmic strategies based on policy requirements, and reason about solution qualities. / Graduate / 0984

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 non-cooperative spectrum sharing environment, the Shannon capacity utility function results in a water-filling solution. In this thesis, the suitability of the water-filling solution is evaluated when using non-Gaussian signalling first in a frequency non-selective 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 well-known spectrum agility, rate and transmit power adaptation when performing spectrum sharing.

Universiẗat, Diss., 2006--Trier.

OLIVEIRA, Ana Karolinna Maia de. Estudo de casos de complexidade de colorações gulosa de vértices e de arestas. 2011. 58 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T18:03:48Z No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:34:49Z (GMT) No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) / Made available in DSpace on 2016-07-13T12:34:49Z (GMT). No. of bitstreams: 1 2011_dis_akmoliveira.pdf: 520341 bytes, checksum: b0c0d48f19d7c3e376c2c79c3a815b08 (MD5) Previous issue date: 2011 / The vertices and edges colorings problems, which consists in determine the smallest number of colors needed to color the vertices and edges of a graph, respectively, so that adjacent vertices and adjacent edges, respectively, have distinct colors, are computationally hard problems and recurring subject of research in graph theory due to numerous practical problems they model. In this work, we study the worst performance of greedy algorithms for coloring vertices and edges. The greedy algorithm has the following general principle: to receive, one by one, the vertices (respect. edges) of the graph to be colored by assigning always the smallest possible color to the vertex (resp. edge) to be colored. We note that so greedy coloring the edges of a graph is equivalent to greedily coloring its line graph, this being the greatest interest in research on greedy edges coloring. The worst performance of the Algorithms is measured by the greatest number of colors they can use. In the case of greedy vertex coloring, this is the number of Grundy or greedy chromatic number of the graph. For the edge coloring, this is the greedy chromatic index or Grundy index of the graph. It is known that determining the Grundy number of any graph is NP-hard. The complexity of determining the Grundy index of any graph was however an open problem. In this dissertation, we prove two complexity results. We prove that the Grundy number of a (q,q−4)-graph can be determined in polynomial time. This class contains strictly the class of cografos P4-sparse for which the same result had been established. This result generalizes so those results. The presented algorithm uses the primeval decomposition of graphs, determining the parameter in linear time. About greedy edge coloring, we prove that the problem of determining the Grundy index is NP-complete for general graphs and polynomial for catepillar graphs, implying that the Grundy number is polynomial for graphs of line of caterpillars. More specifically, we prove that the Grundy index of a caterpillar is D or D+1 and present a polynomial algorithm to determine it exactly. / Os problemas de coloracão de vértices e de arestas, que consistem em determinar o menor número de cores necessárias para colorir os vértices e arestas de um grafo, respectivamente, de forma que vértices adjacentes e arestas adjacentes, respectivamente, possuem cores distintas, são problemas computacionalmente difíceis e são objeto de pesquisa recorrente em teoria do grafos em virtude de inúmeros problemas práticos que eles modelam. No presente trabalho, estudamos o pior desempenho dos algoritmos gulosos de coloração de vértices e de arestas. O algoritmo guloso tem o seguinte princípio geral: receber, um a um, os vértices (respect. as arestas) do grafo a ser colorido, atribuindo sempre a menor cor possível ao vértice (resp. aresta) a ser colorido. Observamos que colorir de forma gulosa as arestas de um grafo equivale a colorir de forma gulosa o seu grafo linha, tendo sido este o maior interesse na pesquisa em coloração gulosa de arestas. O pior desempenho dos algoritmos é medido pelo maior número de cores que eles podem utilizar. No caso da coloração gulosa de vértices, esse é o número de Grundy ou número cromático guloso do grafo. No caso da coloração de arestas, esse é o íındice cromático guloso ou íındice de Grundy do grafo. Sabe-se que determinar o número de Grundy de um grafo qualquer é NP-difícil. A complexidade de determinar o índice de Grundy de um grafo qualquer era entretanto um problema em aberto. Na presente dissertação, provamos dois resultados de complexidade. Provamos que o número de Grundy de um grafo (q,q−4) pode ser determinado em tempo polinomial. Essa classe contém estritamente a classe dos cografos e P4-esparsos para os quais o mesmo resultado havia sido estabelecido. Esse resultado generaliza portanto aqueles resultados. O algoritmo apresentado usa a decomposição primeval desses grafos, determinando o parâmetro em tempo linear. No que se refere à coloração de arestas, provamos que o problema de determinar o índice de Grundy é NP-completo para grafos em geral e polinomial para grafos caterpillar, implicando que o número de Grundy é polinomial para os grafos linha desses. Mais especificamente provamos que o índice de Grundy dos caterpillar é D ou D+1 e apresentamos um algoritmo polinomial para determiná-lo exatamente.