Many problems of practical significance are known to be NP-hard, and hence, are unlikely to be solved by polynomial-time algorithms. There are several ways to cope with the NP-hardness of a certain problem. The most popular approaches include heuristic algorithms, approximation algorithms, and randomized algorithms. Recently, parameterized computation and complexity have been receiving a lot of attention. By taking advantage of small or moderate parameter values, parameterized algorithms provide new venues for practically solving problems that are theoretically intractable. In this dissertation, we design efficient parameterized algorithms for several wellknown NP-hard problems and prove strong lower bounds for some others. In doing so, we place emphasis on the development of new techniques that take advantage of the structural properties of the problems. We present a simple parameterized algorithm for Vertex Cover that uses polynomial space and runs in time O(1.2738k + kn). It improves both the previous O(1.286k + kn)-time polynomial-space algorithm by Chen, Kanj, and Jia, and the very recent O(1.2745kk4 + kn)-time exponential-space algorithm, by Chandran and Grandoni. This algorithm stands out for both its performance and its simplicity. Essential to the design of this algorithm are several new techniques that use structural information of the underlying graph to bound the search space. For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an “almost-global” analysis of the search tree. We also show that an important structural property of the underlying graphs – the graph genus – largely dictates the computational complexity of some important graph problems including Vertex Cover, Independent Set and Dominating Set. We present a set of new techniques that allows us to prove almost tight computational lower bounds for some NP-hard problems, such as Clique, Dominating Set, Hitting Set, Set Cover, and Independent Set. The techniques are further extended to derive computational lower bounds on polynomial time approximation schemes for certain NP-hard problems. Our results illustrate a new approach to proving strong computational lower bounds for some NP-hard problems under reasonable conditions.

This dissertation focuses on a comparative study of small-world characteristics in geographical, epidemic, and virtual spaces. Small-world network is the major component of the “new science of networks” that emerged recently in research related to complex networks. It has shown a great potential to model the complex networks encountered in geographical studies. This dissertation, in an attempt to understand the emergence of small-world phenomenon in spatial networks, has investigated the smallworld properties in aforementioned three spaces. Specifically, this dissertation has studied roadway transportation networks at national, metropolitan, and intra-city scales via network autocorrelation methods to investigate the distance effect on the emergence of small-world properties. This dissertation also investigated the effect of small-world network properties on the epidemic diffusion and different control strategies through agent-based simulation on social networks. The ASLevel Internet in the contiguous U.S. has been studied in its relation between local and global connections, and its correspondence with small-world characteristics. Through theoretical simulations and empirical studies on spatial networks, this dissertation has contributed to network science with a new method – network autocorrelation, and better understanding from the perspective of the relation between local and global connections and the distance effect in networks. A small-world phenomenon results from the interplay between the dynamics occurring on networks and the structure of networks; when the influencing distance of the dynamics reaches to the threshold of the network, the network will logically emerge as a small-world network. With the aid of numerical simulation a small-world network has a large number of local connections and a small number of global links. It is also found that the epidemics will take shorter time period to reach largest size on a small-world network and only particular control strategy, such as targeted control strategy, will be effective on smallworld networks. This dissertation bridges the gap between new science of networks and the network study in geography. It potentially contributes to GIScience with new modeling strategy for representing, analyzing, and modeling complexity in hazards prevention, landscape ecology, and sustainability science from a network-centric perspective.

Much research has been done on wireless sensor networks. However, most protocols and algorithms for such networks are based on the ideal model Unit Disk Graph (UDG) model or do not assume any model. Furthermore, many results assume the knowledge of location information of the network. In practice, sensor networks often deviate from the UDG model significantly. It is not uncommon to observe stable long links that are more than five times longer than unstable short links in real wireless networks. A more general network model, the quasi unit-disk graph (quasi-UDG) model, captures much better the characteristics of wireless networks. However, the understanding of the properties of general quasi-UDGs has been very limited, which is impeding the design of key network protocols and algorithms. In this dissertation we study the properties for general wireless sensor networks and develop new topological/geometrical techniques for wireless sensor networking. We assume neither the ideal UDG model nor the location information of the nodes. Instead we work on the more general quasi-UDG model and focus on figuring out the relationship between the geometrical properties and the topological properties of wireless sensor networks. Based on such relationships we develop algorithms that can compute useful substructures (planar subnetworks, boundaries, etc.). We also present direct applications of the properties and substructures we constructed including routing, data storage, topology discovery, etc. We prove that wireless networks based on quasi-UDG model exhibit nice properties like separabilities, existences of constant stretch backbones, etc. We develop efficient algorithms that can obtain relatively dense planar subnetworks for wireless sensor networks. We also present efficient routing protocols and balanced data storage scheme that supports ranged queries. We present algorithmic results that can also be applied to other fields (e.g., information management). Based on divide and conquer and improved color coding technique, we develop algorithms for path, matching and packing problem that significantly improve previous best algorithms. We prove that it is unlikely for certain problems in operation science and information management to have any relatively effective algorithm or approximation algorithm for them.

A celebrated theorem of Savitch [Savitch'70] states that NSPACE(S) is contained in DSPACE(S²). In particular, Savitch gave a deterministic algorithm to solve ST-Connectivity (an NL-complete problem) using O({log}²{n}) space, implying NL (non-deterministic logspace) is contained in DSPACE({log}²{n}). While Savitch's theorem itself has not been improved in the last four decades, several graph connectivity problems are shown to lie between L and NL, providing new insights into the space-bounded complexity classes. All the connectivity problems considered in the literature so far are essentially special cases of ST-Connectivity. In this dissertation, we initiate the study of auxiliary PDAs as graph connectivity problems and define sixteen different "graph realizability problems" and study their relationships. The complexity of these connectivity problems lie between L (logspace) and P (polynomial time). ST-Realizability, the most general graph realizability problem is P-complete. 1DSTREAL(poly), the most specific graph realizability problem is L-complete. As special cases of our graph realizability problems we define two natural problems, Balanced ST-Connectivity and Positive Balanced ST-Connectivity, that lie between L and NL. We study the space complexity of SGSLOGCFL, a graph realizability problem lying between L and LOGCFL. We define generalizations of graph squaring and transitive closure, present efficient parallel algorithms for SGSLOGCFL and use the techniques of Trifonov to show that SGSLOGCFL is contained in DSPACE(lognloglogn). This implies that Balanced ST-Connectivity is contained in DSPACE(lognloglogn). We conclude with several interesting new research directions.

<p>The aim of the thesis is to find out the most suitable channel estimation algorithms for the existing MIMO-OFDM SDR platform. Starting with the analysis of several prevalent channel estimation algorithms, MSE performance are compared under different scenarios. As a result of the hardware independent analysis, the complexvalued matrix computations involved in the algorithms are decomposed to real FLoating-point OPerations (FLOPs). Four feasible algorithms are selected for hardware dependent discussion based on the proposed hardware architecture. The computational latency is exposed as a manner of case study.</p>

This thesis is focused on the limits of performance of large-scale convex optimization algorithms. Classical theory of oracle complexity, first proposed by Nemirovski and Yudin in 1983, successfully established the worst-case behavior of methods based on local oracles (a generalization of first-order oracle for smooth functions) for nonsmooth convex minimization, both in the large-scale and low-scale regimes; and the complexity of approximately solving linear systems of equations (equivalent to convex quadratic minimization) over Euclidean balls, under a matrix-vector multiplication oracle. Our work extends the applicability of lower bounds in two directions: Worst-Case Complexity of Large-Scale Smooth Convex Optimization: We generalize lower bounds on the complexity of first-order methods for convex optimization, considering classes of convex functions with Hölder continuous gradients. Our technique relies on the existence of a smoothing kernel, which defines a smooth approximation for any convex function via infimal convolution. As a consequence, we derive lower bounds for \ell_p/\ell_q-setups, where 1\leq p,q\leq \infty, and extend to its matrix analogue: Smooth convex minimization (with respect to the Schatten q-norm) over matrices with bounded Schatten p-norm. The major consequences of this result are the near-optimality of the Conditional Gradient method over box-type domains (p=q=\infty), and the near-optimality of Nesterov's accelerated method over the cross-polytope (p=q=1). Distributional Complexity of Nonsmooth Convex Optimization: In this work, we prove average-case lower bounds for the complexity of nonsmooth convex ptimization. We introduce an information-theoretic method to analyze the complexity of oracle-based algorithms solving a random instance, based on the reconstruction principle. Our technique shows that all known lower bounds for nonsmooth convex optimization can be derived by an emulation procedure from a common String-Guessing Problem, which is combinatorial in nature. The derived average-case lower bounds extend to hold with high probability, and for algorithms with bounded probability error, via Fano's inequality. Finally, from the proposed technique we establish the equivalence (up to constant factors) of distributional, randomized, and worst-case complexity for black-box convex optimization. In particular, there is no gain from randomization in this setup.

The purpose of this study was to investigate the current perceptions of high school principals regarding their perceived roles, professional development experiences that impacted their careers, and the challenges and frustrations they face when enacting their roles as high school leaders. This qualitative study investigated perceptions of high school principals and addressed three research questions: (1) What are the perceptions of high school principals regarding their role as school leaders? (2) What professional development experiences do high school principals report are most important in impacting their careers? (3) What do high school principals perceive are their greatest challenges and frustrations? Three in-depth qualitative interviews were conducted with each of eight high school principals. The results were based on analysis by the researcher and the two expert panels. The high school principals perceived that they had a tremendous number of roles and responsibilities within their positions. The roles and responsibilities that were identified with the greatest importance were: providing a safe learning environment, ensuring quality teachers and quality instruction, high accountability expectations for all and mandates, and leadership within the school and system. Professional development opportunities and personalized support systems were perceived to be vital to the success of the high school principal.  Principals in the study reported that both formal and informal professional development experiences were beneficial for their improvement as school leaders. The principals perceived that when they created relationships with mentors and established strong networks, they improved the likelihood of sustained support and success. High school principals perceived the greatest challenges were management of time, balancing leadership and management of the school, and navigating the legislative mandates and accountability requirements.  High school principals perceived the greatest frustrations were issues related to time and legislative mandates dictated to them by the local, state, and federal systems. They faced constant pressures that could be directly tied to student achievement and accountability measures. High school principals need to be prepared to assume various roles. Further research may determine if roles and challenges identified by the eight participants mirror other states’ results.

ITC/USA 2014 Conference Proceedings / The Fiftieth Annual International Telemetering Conference and Technical Exhibition / October 20-23, 2014 / Town and Country Resort & Convention Center, San Diego, CA / SOQPSK-TG is a highly bandwidth-efficient constant-envelope modulation so that it has been applied in aeronautical telemetry widely. We develop a simple detection of SOQPSK-TG which is based on a modified OQPSK detection. The simple detection has the advantages of low complexity and good performance. And it's also suitable for other varieties of SOQPSK and FQPSK.

Current literature regarding quality health services frequently identifies interprofessional collaboration (IPC) as essential to patient-centred care, sustainable health systems, and a productive workforce. The IPC literature tends to focus on interprofessionalism and collaboration and pays little attention to the concept of practice, which is thought to be a represented world of objects and processes that have pre-given characteristics practitioners can know cognitively and apply or manage correctly. Many strategies intended to support IPC simplify and codify the complex, contested, and unpredictable day-to-day interactions among interdependent agents that I argue constitute the practices of a community. These strategies are based in systems thinking, which understand the system as distinct from experience and subject to rational, linear logic. In this thinking, a leader can step outside of the system to develop an ideal plan, which is then implemented to unfold the predetermined ideal future. However, changes in health services and healthcare practices are often difficult to enact and sustain.This thesis problematises the concept of ‘practice’, and claims practices as thoroughly social and emergent phenomenon constituted by interdependent and iterative processes of representation (policies and practice guidelines), signification (sense making through negotiation and reflective and reflexive practices), and improvisation (acting into the circumstances that present at the point and in the moments of care). I argue that local and population-wide patterns are negotiated and iteratively co-expressed through relations of power, values, and identity. Moreover, practice (including the practice of leadership or consulting) is inherently concerned with ethics, which I also formulate as both normative and social/relational in nature. I argue that theory and practice are not separate but paradoxical phenomena that remain in generative tension, which in healthcare is often felt as tension between what we should do (best practice) and what we actually do (best possible practice in the contingent circumstances we find ourselves in). I articulate the implications this has for how knowledge and knowing are understood, how organisations change, and how the role of an internal practice consultant is understood. An important implication is that practice-based evidence and evidence-based practice are iterative and coexpressed(not sequential), and while practice is primordial, it is not privileged over theory.I propose that a practice consultant could usefully become a temporary participant in the practices of a particular community. Through a position of ‘involved detachment’, a consultant can more easily notice and articulate the practices of a community that for participants are most often implicit and taken for granted. Reflective and reflexive consideration of what is taken for granted may change conversations and thus be transformative.

This dissertation is a case study dealing with a school development project that took place in an upper secondary school as a result of a merger of two schools with different cultures. The project used a method called “Frirumsmodellen” and was planned to be conducted in three steps. The first was to carry out a cultural analysis in order to map the preconditions to start a school development project. The second was to carry out concrete actions and finally study eventual effects from such activities by doing a second cultural analysis. My role was to be a supervisor in the school development work, but at the same time study how this work was conducted and its impact in the ordinary school day. The dissertation takes its departure in the fact that schools are political governed. The mission of schools is never neutral; it is always an expression of behind laying social forces, ideologies and ideals of the contemporary society. Of this reason, there is a close connection between the macro political level and the micro political level. Another point of departure is the transition from a modern to a post modern society that gives the character to the changes that take place in schools. Steering of schools has partly been treated as a technical implementation problem. Schools contain on going conflicts between different interest groups that, more or less regularly, end up in educational reforms. These reforms generate school development activities in the single school. Undoubtedly, this makes school development to a complex process. At a rather late stage of the study I decided not to fulfil my task to follow the original plan. I instead let the school development project as a model to be in focus. The over all purpose was formulated: How is it possible to understand what happened in the school development project in the Falkgymnasiet and why was it not possible to carry it out as it was said in the project plan? To interpret what took place during the project I did create an interpretation frame of implementation and complexity theory that also made it possible to critically scrutinise the “Frirumsmodellen”. Already in an early stage of the process it was obvious that the “Frirumsmodellen” did not supply any tools to use and it became disconnected from the project. The project in it selves was marginalised and made invisible. The headmaster used the situation to change things she thought were important to develop. As a result, things happened, but most of the involved people did not at first hand connect this to the project. It is, of course, difficult in detail to say what caused what. The complexity theory successively made the hidden patterns revealed, hidden unofficial potentates visible, as well as unpredictable conditions that generated reactions from the personnel in front of a development work. Together this was rather efficient obstacles for not changing this school. I also discuss school development and implementation problems on a general level, for example, the possibility to transform a top-down initiated project to be bottom-up driven and using project as a tool for school development work. It was obvious that headmasters and teachers must be prepared to handle the ideological dimensions of problems schools have to face. Consequently, development work is about making problems visible and to handle these in the intersection point between the intentions of educational policies, pedagogical researchers, school administrators, headmasters, teachers and pupils. The ideological dimension also contains an existential issue. Do I as a teacher share the intentions for the development work? If not, how must I act? / <p>Finns som talbok. Inläst ur Växjö University Press, 2008 av talsyntes. Talboken omfattar 1 CD-ROM (18 tim., 33 min.)</p>