220 research outputs found
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
Full text linkThe 2-opt heuristic is a simple local search heuristic for the Travelling Salesperson Problem (TSP). Although it usually performs well in practice, its worst-case running time is poor. Attempts to reconcile this difference have used smoothed analysis, in which adversarial instances are perturbed probabilistically. We are interested in the classical model of smoothed analysis for the Euclidean TSP, in which the perturbations are Gaussian. This model was previously used by Manthey \& Veenstra, who obtained smoothed complexity bounds polynomial in , the dimension , and the perturbation strength . However, their analysis only works for . The only previous analysis for was performed by Englert, R\"oglin \& V\"ocking, who used a different perturbation model which can be translated to Gaussian perturbations. Their model yields bounds polynomial in and , and super-exponential in . As no direct analysis existed for Gaussian perturbations that yields polynomial bounds for all , we perform this missing analysis. Along the way, we improve all existing smoothed complexity bounds for Euclidean 2-opt
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
Full text linkWe analyze the running time of the Hartigan-Wong method, an old algorithm for the k-means clustering problem. First, we construct an instance on the line on which the method can take steps to converge, demonstrating that the Hartigan-Wong method has exponential worst-case running time even when k-means is easy to solve. As this is in contrast to the empirical performance of the algorithm, we also analyze the running time in the framework of smoothed analysis. In particular, given an instance of n points in d dimensions, we prove that the expected number of iterations needed for the Hartigan-Wong method to terminate is bounded by k^{12kd} \cdot \poly(n, k, d, 1/\sigma) when the points in the instance are perturbed by independent d-dimensional Gaussian random variables of mean 0 and standard deviation
Complexity of Local Search for Euclidean Clustering Problems
Full text linkWe show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-hard. First, we show that the Hartigan-Wong method, which is essentially the Flip heuristic, for k-Means clustering is PLS-hard, even when k = 2. Second, we show the same result for the Flip heuristic for Max Cut, even when the edge weights are given by the (squared) Euclidean distances between the points in some set ⊆ R^d; a problem which is equivalent to Min Sum 2-Clustering
The anti-nuclear power movement and discourses of energy justice/ Jesse P. Van Gerven.
No full textIncludes bibliographical references."This study analyzes anti-nuclear power organizations' claims regarding public financing for new nuclear construction, issues associated with the management of high-level radioactive waste, and other campaigns to increase the safety of nuclear facilities. This leads the author to the identification of general principals of energy justice"--Introduction -- Federal "Loan Guarantees" for Financing New Nuclear Reactor Construction -- High-Level Radioactive Waste Management -- State/Local Financing of New Nuclear Reactor Construction and the Fights for Increased Nuclear Safety -- Conclusion.1 online resourc
The invisible artist: Arrangers in popular music (1950-2000): Their contribution and techniques
Full text linkThis thesis was submitted for the degree of Doctor of Philosophy and was awarded by Brunel University.This thesis is based on the research conducted by the author for the series,
Richard Niles' History of Pop Arranging, seven thirty-minute documentary
programmes for BBC Radio 2, researched, written and presented by the author and
broadcast in 2003. It also draws on interviews conducted by the author (and other
research) between 2002 and 2007 both for the radio series and for this thesis and on
the author's experience as a professional arranger in popular music working with
many of the genre's significant recording artists including Paul McCartney, Ray
Charles, Cher, Tina Turner, Westlife, Tears For Fears, Dusty Springfield, James
Brown, Pet Shop Boys, Kylie Minogue and producers including Trevor Hom, Steve
Lipson, Steve Mac and Steve Anderson.
It will be argued that the role of the arranger in popular music has often been
undervalued and that during a critical period of popular music history (1950-2000)
arrangers played a significant part in the evolution of musical content. This thesis is,
to the best of the author's knowledge, the first time (apart from the above mentioned
documentary) the subject has ever been examined. The arranger is "invisible" because musical arrangers are often un-credited on
record liner notes or in books or articles concerning popular music. A considerable
amount of research has been necessary to determine who wrote many of the
arrangements considered herein. Motown's Berry Gordy purposely kept the names of
musicians and arrangers off the records because he feared others might 'poach' the
trademark 'Motown Sound'. Other record labels considered the job of the arranger to
be reminiscent of an earlier era, diluting the Rock 'n' Roll image of emotion and
spontanaeity they wished to promote. Some producers and recording artists disliked
sharing credit for their work. Motown arranger David Van dePitte told the author that
arranging was "thankless and anonymous - a very service-oriented profession where
others often take credit for what you've done." Arranging has therefore remained an
intrinsically unseen art created by 'invisible' artists. By analyzing many recordings,
revealing the techniques and concepts they have used in their work to create popular
records, arrangers and their art will be made more 'visible'
"Get off the track!" A song for emancipation, sung by The Hutchinsons, . . .
No full textAn illustrated sheet music cover for an abolitionist song composed by Jesse Hutchinson, Jr. The song is dedicated to antislavery editor Nathaniel Peabody Rogers, "As a mark of esteem for his intrepidity in the cause of Human Rights." It is illustrated with an allegory of the triumph of abolitionism. In a landscape a railroad car, "Immediate Emancipation," is drawn by a locomotive named "Liberator" and followed by another locomotive, the "Repealer," which pulls a second car "Liberty Votes and Ballot Boxes." The "Liberator" was the name of a prominent antislavery newspaper published in Boston by William Lloyd Garrison. "Repealer" probably refers to the Irish insurgent movement in support of the repeal of the Legislative Union, a cause with which many abolitionists in the United States were allied. Flags bearing the names of two other abolitionist publications, the "Herald of Freedom" and "American Standard" (i.e., Rogers's" National Anti-slavery Standard), fly from the "Emancipation" car. The trains approach a bend in the track, nearing a station where a number of people gather to welcome them. Beyond the station is a church. In the distance two other trains, one marked "Van" and the other "Clay," crash and their passengers flee. These allude to Democrat and Whig presidential hopefuls Martin Van Buren and Henry Clay. The reference to Van Buren suggests that the music-sheet appeared before the Democratic convention in May, when James K. Polk, not Van Buren, received the party's presidential nomination.Entered . . . 1844 by J. Hutchinson.Thayer & Co's. Lith Boston.Title appears as it is written on the item.Published in: American political prints, 1766-1876 / Bernard F. Reilly. Boston : G.K. Hall, 1991, entry 1844-52
Rigorous analysis of local search heuristics
Full text linkLocal search heuristics are standard methods in the optimizer's toolbox. These algorithms take as an input a candidate solution to an optimization problem and iteratively compute better solutions. Heuristics typically provide close-to-optimal solutions in much less running time than exact or approximation algorithms. Despite their practical usefulness, local search heuristics often have poor performance in the worst case. For many problems we know of instances where commonly used heuristics take prohibitively long to return a solution, or where they may return solutions that are far from optimal. This considerable gap between theory and practice is not satisfactory, as we would like to have some theoretical justification for using local search heuristics in practice. This dissertation broadly aims to enhance our understanding of local search heuristics. We analyze several heuristics using rigorous mathematical tools. We focus on three computational problems: the Travelling Salesperson Problem (TSP), k-Means clustering, and Max Cut. We consider these heuristics from the perspective of worst-case and beyond-worst-case analysis.For the TSP, we perform a smoothed analysis of the well-known 2-opt heuristic, improving and simplifying previous results for the Euclidean TSP. We then consider two polynomial-time variants of 2-opt, showing that one has poor approximation performance while the other performs similary to 2-opt. We moreover analyze the complexity of counting 2-optimal tours, and estimate the number of such tours in random instances. For k-Means clustering, we rigorously analyze the Hartigan-Wong method. This heuristic performs well in practice, but little was previously known about it theoretically. We show that even in one-dimensional instances, where k-Means can be solved optimally in polynomial time, the Hartigan-Wong method can take exponential time to find locally optimal clusterings. We also show that the heuristic leads to a PLS-complete local search problem. To augment these results we also perform the first smoothed analysis of the Hartigan-Wong method.Finally, we analyze the Flip heuristic for Max Cut, and show that also this simple heuristic yields a PLS-complete local search problem even in Euclidean instances
Key factors in team collaboration: A qualitative study to determine the team effectiveness of an inter-organisational, international project based integrated design team
No full textAim: The aim of this thesis is to investigate team effectiveness in the field of construction. With this study, influential factors on team collaboration between different companies and within teams will be defined. By defining these factors, project managers of comparable project-based integrated design teams can improve the team collaboration within the project team and with that optimize their team’s effectiveness. The research focuses on a big complex building project, which will be used as a transportation hub, in the Netherlands. Research question: What are key factors which influence team collaboration of a project-based integrated design team in context of a large-scale complex building project, influenced by fast growth, different cultures and a changing scope? Methodology: The factors are explored by conducting a single case study research. The starting point was a literature study towards team effectiveness. The outcome of this study was used as input for the case study research. The case study was used to collect data, the data was generated by conducting semistructured interviews. After these interviews were conducted, observations, off the record conversations and inspection of restricted documents were used to discuss and validate conclusions. Findings: The literature research concluded in the backbone of this research. The IMOI model of Ilgen et al. (2005), structure the inputs, mediators and outcomes of the team’s effectiveness. The model is used to determine different factors that could influence the team collaboration. The case study research determined three events which are important for the further course of the project. Due to a lack of management during these events, the client in combination with leading members of the team had to overrule the management layer. The events; assembling the team, collaboration during the project and involving team members have to be managed with both organizational and interpersonal skills. Limitations of the research: It is a qualitative research; therefore, the research is always subject to biased opinions and interpretations of the data. Besides that, the research is conducted on only one case and therefore not automatically representative for all comparable cases. However, the factors resulting from this study need to be kept in mind, due to the fact that it will always be factors that influence the team collaboration, not said that they have to be the most influential for every comparable project-based integrated design team. Practical implications: The research addresses factors that affect the team collaboration of a project-based integrated design team. These factors should be taken into account when starting a comparable project team. Even though the case study of this research concluded with these factors, it is not excluded that there are more factors that influence the team collaboration of a project-based integrated design team. Therefore, more studies should be conducted in this area of research. Scientific relevance: There are a lot of studies conducted towards the team effectiveness of composed teams, however, more research is needed to define the factors that influence the team collaboration of a projectbased team. This research could be used as a starting point for further research, while it is one of the first studies conducted on a project-based team of this size and complexity, subjected to designing a big complex building project. Keywords: Project-based integrated design team, team collaboration, team effectiveness, project management, IMOI framework.Architecture, Urbanism and Building Sciences | Management in the Built Environmen
Rotational stiffness in compliant mechanisms: theory, method and application
No full textCompliant mechanisms accomplish their function due to the elastic deformation of their elements rather than using the relative motion of rigid bodies. Thereby the drawbacks of sliding friction, including wear and hysteresis are eliminated. Besides that compliant mechanisms allows monolithic production which facilitates cost reduction and miniaturization possibilities. However, the integration of functions into fewer parts requires the simultaneous design of motion and force behaviour, causing a difficult design process.The commonly used design methods ('rigid-body replacement' and 'freedom and constraint topologies') try to bypass this difficult design process by considering the motion behaviour first. However this can lead to bad force behaviour in the end. A requirement that is often causing overcomplicated and bulky designs (because of an ill-considered kinematic structure) is the requirement of high rotational stiffness.To facilitate the difficult design of high rotational stiffness structures a different design method is proposed. First a general design class with high rotational stiffness is developed. Based on this design class the designer can select a kinematic structure that fits the high rotational stiffness requirement. From here on the designer can continue with the commonly used design methods.To show the power of the proposed design method a novel homokinetic joint is designed. Measurements are done to verify the most important properties of the design
A framework to find applications for organic molecules
No full textInnovation is an important determinant for success in a fast changing world. For innovation to take place, scientific knowledge that has a proven working principle needs to find an application. The process in which applications are generated or identified has been identified as an important aspect of the innovation process. However, scientific literature on application generation or identification is underdeveloped. The aim of this thesis was to develop a framework to generate or identify applications for organic molecules in a systematic way. This has been formulated into a research question as “Can a framework be developed to systematically search for applications for organic molecules?”. Before this framework for organic molecules was developed, first a general framework to generate or identify applications for technology was created. Apart from the main research question, three sub research questions are answered in this research: Can a framework to systematically search for applications for technology be developed? How can such a framework be translated to a framework for organic molecules? How can this/these framework(s) be validated? The framework was created using a design approach. The thesis draws on interviews with experts, scientific literature on application generation/identification frameworks and a discussion with experts. In the preliminary literature study, the notion that the literature on the subject of application generation or identification is underdeveloped was confirmed. The available literature provided insufficient base to build this thesis, so a design approach was taken as alternative. The first step in this approach was a series of interviews with experts on innovation and application generation/identification. With the data from these interviews, a first version of the general framework was created. This first version was validated and improved by comparing it to frameworks from literature, by conducting a second series of interviews and by a discussion with experts. The next step envisioned in the research was a translation of the general framework into a framework that can be used to generate or identify applications for organic molecules. A start was made on the translation of the framework by providing methods that can be used in subsequent research to translate the framework. The translation chapter used information from the second series of interviews as a starting point. Following this research, four recommendations were made for future research project. The first recommendation is to further develop the framework created in this research project, for example by exploring creativity methods. Secondly, it is recommended to conduct a full systematic literature review, using the vocabulary learned throughout this thesis. Thirdly, the framework created in this thesis should be translated. Before translation can take place, it has to be researched what the best method for this translation is. The translation methods provided in this thesis could be used. Alternatively, new methods for translation could be devised and implemented. Finally, in future research, several concept used in this research should be defined more carefully. Obtaining more clear and workable definitions for these concept will decrease the ambiguity of future research using these concepts. In conclusion, in this thesis, a framework to systematically generate or identify applications for technology (or rather, a concept in between scientific knowledge and technology) has been developed. Recommendations have been provided on how this framework could be further improved. On top of that, this research proposes methods for translation of this framework into a framework to systematically generate or identify applications for organic molecules. The actual translation has to take place in subsequent research.Management of Technology (MoT
- …
