Spelling suggestions: "subject:"[een] COMBINATORIAL OPTIMIZATION"" "subject:"[enn] COMBINATORIAL OPTIMIZATION""
61 |
Optimality and approximability of the rectangle covering problemChung, Yau-lin., 鍾有蓮. January 2004 (has links)
published_or_final_version / abstract / toc / Mathematics / Master / Master of Philosophy
|
62 |
Inverse Parametric Alignment for Accurate Biological Sequence ComparisonKim, Eagu January 2008 (has links)
For as long as biologists have been computing alignments of sequences, the question of what values to use for scoring substitutions and gaps has persisted. In practice, substitution scores are usually chosen by convention, and gap penalties are often found by trial and error. In contrast, a rigorous way to determine parameter values that are appropriate for aligning biological sequences is by solving the problem of Inverse Parametric Sequence Alignment. Given examples of biologically correct reference alignments, this is the problem of finding parameter values that make the examples score as close as possible to optimal alignments of their sequences. The reference alignments that are currently available contain regions where the alignment is not specified, which leads to a version of the problem with partial examples.In this dissertation, we develop a new polynomial-time algorithm for Inverse Parametric Sequence Alignment that is simple to implement, fast in practice, and can learn hundreds of parameters simultaneously from hundreds of examples. Computational results with partial examples show that best possible values for all 212 parameters of the standard alignment scoring model for protein sequences can be computed from 200 examples in 4 hours of computation on a standard desktop machine. We also consider a new scoring model with a small number of additional parameters that incorporates predicted secondary structure for the protein sequences. By learning parameter values for this new secondary-structure-based model, we can improve on the alignment accuracy of the standard model by as much as 15% for sequences with less than 25% identity.
|
63 |
A primal-dual algorithm for the maximum charge problem with capacity constraintsBhattacharjee, Sangita, University of Lethbridge. Faculty of Arts and Science January 2010 (has links)
In this thesis, we study a variant of the maximum cardinality matching problem known as
the maximum charge problem. Given a graph with arbitrary positive integer capacities assigned
on every vertex and every edge, the goal is to maximize the assignment of positive
feasible charges on the edges obeying the capacity constraints, so as to maximize the total
sum of the charges. We use the primal-dual approach. We propose a combinatorial algorithm
for solving the dual of the restricted primal and show that the primal-dual algorithm
runs in a polynomial time. / ix, 96 leaves : ill. ; 29 cm
|
64 |
Hybrid column generation for large network routing problems : with implementations in airline crew schedulingShaw, Tina L. 05 1900 (has links)
No description available.
|
65 |
Empirical learning methods for the induction of knowledge from optimization modelsKirschner, Kenneth J. 08 1900 (has links)
No description available.
|
66 |
A new rank based version of the Ant System. A computational study.Bullnheimer, Bernd, Hartl, Richard F., Strauß, Christine January 1997 (has links) (PDF)
The ant system is a new meta-heuristic for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. It was first proposed for tackling the well known Traveling Salesman Problem (TSP), but has been also successfully applied to problems such as quadratic assignment, job-shop scheduling, vehicle routing and graph coloring.In this paper we introduce a new rank based version of the ant system and present results of a computational study, where we compare the ant system with simulated annealing and a genetic algorithm on several TSP instances. It turns out that our rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior. (author's abstract) / Series: Working Papers SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
|
67 |
Combinatorial and probabilistic methods in biodiversity theoryFaller, Beáta January 2010 (has links)
Phylogenetic diversity (PD) is a measure of species biodiversity quantified by how
much of an evolutionary tree is spanned by a subset of species. In this thesis, we study
optimization problems that aim to find species sets with maximum PD in different scenarios,
and examine random extinction models under various assumptions to predict the
PD of species that will still be present in the future.
Optimizing PD with Dependencies is a combinatorial optimization problem in
which species form an ecological network. Here, we are interested in selecting species
sets of a given size that are ecologically viable and that maximize PD. The NP-hardness
of this problem is proved and it is established which special cases of the problem are
computationally easy and which are computationally hard. It is also shown that it is
NP-complete to decide whether the feasible solution obtained by the greedy algorithm is
optimal. We formulate the optimization problem as an integer linear program and find
exact solutions to the largest food web currently in the empirical literature. In addition,
we give a generalization of PD that can be used for example when we do not know the
true evolutionary history. Based on this measure, an optimization problem is formulated.
We discuss the complexity and the approximability properties of this problem.
In the generalized field of bullets model (g-FOB), species are assumed to become
extinct with possibly different probabilities, and extinction events are independent. We
show that under this model the distribution of future phylogenetic diversity converges to
a normal distribution as the number of species grows. When extinction probabilities are
influenced by some binary character on the tree, the state-based field of bullets model
(s-FOB) represents a more realistic picture. We compare the expected loss of PD under
this model to that under the associated g-FOB model and find that the former is always
greater than or equal to the latter. It is natural to further generalize the s-FOB model to
allow more than one binary character to affect the extinction probabilities. The expected
future PD obtained for the resulting trait-dependent field of bullets model (t-FOB) is
compared to that for the associated g-FOB model and our previous result is generalized.
|
68 |
Applications of submodular minimization in machine learning /Narasimhan, Mukund, January 2007 (has links)
Thesis (Ph. D.)--University of Washington, 2007. / Includes bibliographical references (p. 134-142).
|
69 |
Using determinant and cycle basis schemes in genetic algorithms for graph and network applications /Abuali, Faris Nabih. January 1995 (has links)
Thesis (Ph.D.)--University of Tulsa, 1995. / Includes bibliographical references (leaves 118-121).
|
70 |
Artificial intelligence architectures for classifying conjoined dataPierrot, Henri Jan. January 2007 (has links)
Thesis (MSc) - Information and Communication Technology, Swinburne University of Technology, 2007. / Submitted in partial fulfilment of the requirements for the degree of Master of Science (IT), [Information and Communication Technology], Swinburne University of Technology - 2007. Typescript. Includes bibliographical references.
|
Page generated in 0.0331 seconds