By the emergence of electronic commerce and low transaction costs on the Internet, an interest in the design of new auction mechanisms has been arisen. Recently many researchers in computer science, economics, business, and game theory have presented many valuable studies on the subject of online auctions, and auctions theory. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging ones. Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item multi-unit situations where the agents&rsquo / valuations of the items are not additive. However, determining the winners to maximize the revenue is NP-complete. In this study, we first analyze the existing approaches for combinatorial auction problem. Based on this analysis, we then choose three different approaches, which are search approach, descending simultaneous auctions approach, and IP (Integer Programming) formulation approach to build our models. The performances of the models are compared using computer simulations, where we model bandwidth allocation system. Finally a combinatorial auction tool is built which can be used for online auctions and e-procurement systems.

The tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a tree structure. In this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface. In the first part of this thesis we develop a geometric description of tangles in graphs embedded on a fixed surface (tangles are the obstructions for low branch-width), generalizing a result of Robertson and Seymour. We use this result to establish a relationship between the branch-width of an embedded graph and the carving-width of an associated graph, generalizing a result for the plane of Seymour and Thomas. We also discuss how these results relate to the polynomial-time algorithm to determine the branch-width of planar graphs of Seymour and Thomas, and explain why their method does not generalize to surfaces other than the sphere. We also prove a result concerning the class C_2k of minor-minimal graphs of branch-width 2k in the plane, for an integer k at least 2. We show that applying a certain construction to a class of graphs in the projective plane yields a subclass of C_2k, but also show that not all members of C_2k arise in this way if k is at least 3. The last part of the thesis is concerned with applications of graphs of bounded tree-width to the Traveling Salesman Problem (TSP). We first show how one can solve the separation problem for comb inequalities (with an arbitrary number of teeth) in linear time if the tree-width is bounded. In the second part, we modify an algorithm of Letchford et al. using tree-decompositions to obtain a practical method for separating a different class of TSP inequalities, called simple DP constraints, and study their effectiveness for solving TSP instances.

Graphs are a fundamental and widely-used abstraction for representing data. We can analytically study interesting aspects of real-world complex systems such as the Internet, social systems, transportation networks, and biological interaction data by modeling them as graphs. Graph-theoretic and combinatorial problems are also pervasive in scientific computing and engineering applications. In this dissertation, we address the problem of analyzing large-scale complex networks that represent interactions between hundreds of thousands to billions of entities. We present SNAP, a new high-performance computational framework for efficiently processing graph-theoretic queries on massive datasets. Graph analysis is computationally very different from traditional scientific computing, and solving massive graph-theoretic problems on current high performance computing systems is challenging due to several reasons. First, real-world graphs are often characterized by a low diameter and unbalanced degree distributions, and are difficult to partition on parallel systems. Second, parallel algorithms for solving graph-theoretic problems are typically memory intensive, and the memory accesses are fine-grained and highly irregular. The primary contributions of this dissertation are the design and implementation of novel parallel graph algorithms for traversal, shortest paths, and centrality computations, optimized for the small-world network topology, and high-performance multithreaded architectures and multicore servers. SNAP (Small-world Network Analysis and Partitioning) is a modular, open-source framework for the exploratory analysis and partitioning of large-scale networks. With SNAP, we demonstrate the capability to process massive graphs with billions of vertices and edges, and achieve up to two orders of magnitude speedup over state-of-the-art network analysis approaches. We also design a new parallel computing benchmark for characterizing the performance of graph-theoretic problems on high-end systems; study data representations for dynamic graph problems on parallel systems; and apply algorithms in SNAP to solve real-world problems in social network analysis and systems biology.

We study the K-theory and cohomology of spaces of aperiodic and repetitive tilings with finite local complexity. Given such a tiling, we build a spectral sequence converging to its K-theory and define a new cohomology (PV cohomology) that appears naturally in the second page of this spectral sequence. This spectral sequence can be seen as a generalization of the Leray-Serre spectral sequence and the PV cohomology generalizes the cohomology of the base space of a Serre fibration with local coefficients in the K-theory of its fiber. We prove that the PV cohomology of such a tiling is isomorphic to the Cech cohomology of its hull. We give examples of explicit calculations of PV cohomology for a class of 1-dimensional tilings (obtained by cut-and-projection of a 2-dimensional lattice). We also study the groupoid of the transversal of the hull of such tilings and show that they can be recovered: 1) from inverse limit of simpler groupoids (which are quotients of free categories generated by finite graphs), and 2) from an inverse semi group that arises from PV cohomology. The underslying Delone set of punctures of such tilings modelizes the atomics positions in an aperiodic solid at zero temperature. We also present a study of (classical and harmonic) vibrational waves of low energy on such solids (acoustic phonons). We establish that the energy functional (the "matrix of spring constants" which describes the vibrations of the atoms around their equilibrium positions) behaves like a Laplacian at low energy.

We study the facial structure of the independent set polytope using the concept of conflict hypergraphs. A conflict hypergraph is a hypergraph whose vertices correspond to the binary variables, and edges correspond to covers in the constraint matrix of the independent set polytope. Various structures such as cliques, odd holes, odd anti-holes, webs and anti-webs are identified on the conflict hypergraph. These hypergraph structures are shown to be generalization of traditional graph structures. Valid inequalities are derived from these hypergraph structures, and the facet defining conditions are studied. Chvatal-Gomory ranks are derived for odd hole and clique inequalities. To test the hypergraph cuts, we conduct computational experiments on market-share (also referred to as market-split) problems. These instances consist of 100% dense multiple-knapsack constraints. They are small in size but are extremely hard to solve by traditional means. Their difficult nature is attributed mainly to the dense and symmetrical structure. We employ a special branching strategy in combination with the hypergraph inequalities to solve many of the particularly difficult instances. Results are reported for serial as well as parallel implementations.

The research work reported in the thesis deals with the development of dynamic covalent systems and their applications in evaluation and screening of protein-ligands and enzyme inhibitors, as well as in synthetic methodologies. The thesis is divided into four parts as described below. In part one, synthetic methodologies to access 3-functionalized phthalides and 3-thioisoindolinones using the concept of cascade reactions are demonstrated. Efficient syntheses of the target products are designed and performed in one-pot process under mild reaction conditions.  In part two, phosphine-catalyzed disulfide metathesis for the generation of dynamic carbohydrate system in aqueous solution is demonstrated. In the presence of biological target (Concanavalin A), the optimal dynamic ligand is successfully identified in situ by the 1H STD-NMR spectroscopy. In part three, lipase-catalyzed resolutions of dynamic reversible systems using reversible cyanohydrin and hemithioacetal reactions in one-pot processes are demonstrated. The dynamic systems are generated under thermodynamic control in organic solution and subsequently resolved by lipase-mediated resolution under kinetic control. The resolution processes resulted in the lipase-selected substrates with high structural and stereochemical specificities. In the last part, dynamic fragment-based strategy is presented using β-galactosidase as a model target enzyme. Based on our previous study, the best dynamic inhibitor of β-galactosidase was identified using 1H STD-NMR technique from dynamic hemithioacetal systems. The structure of the dynamic inhibitor is tailored by fragment linking and optimization processes. The designed inhibitor structures are then synthesized and tested for inhibition activities against β-galactosidase. / QC 20110526

Millions of years of evolution have resulted in an immense number of different proteins, which participate in virtually every process within cells and thus are of utmost importance for allknown forms of life. In addition, there are several examples of natural proteins which have found use in applications outside their natural environment, such as the use of enzymes infood industry and washing powders or the use of antibodies in diagnostic, bioseparation or therapeutic applications. To improve the performance of proteins in such applications, anumber of techniques, all collectively referred to as ‘protein engineering’, are performed in thelaboratory.Traditionally, methods involving ‘rational design’, where a few alterations are introduced atspecific protein locations to hopefully result in expected improvements have been applied.However, the use of more recent techniques involving a simultaneous construction of a large number of candidate variants (protein libraries) by various diversification principles, fromwhich rare clones showing enhanced properties can be isolated have contributed greatly to thefield of protein engineering.In the present thesis, different protein traits of biotechnological importance have beenaddressed for improvements by the use of such methods, in which there is a crucial need tomaintain a clonal link between the genotype and the phenotype to allow an identification of protein library members isolated by virtue of their functional properties. In all protein library investigations included in this thesis this coupling has been obtained by Escherichia coli bacterialcell-membrane compartmental confinement.In a first study, a combination of error prone PCR and gene-shuffling was applied to the Tobacco Etch Virus (TEV)-protease gene in order to produce collections from which genesencoding variants showing an enhanced soluble expression of the enzyme frequently used inbiotechnology to cleave fusion proteins were identified. Using Green Fluorescence Protein(GFP)-based cell fluorescence analysis, a clone with a five-fold increase in the yield of solubly produced protein was successfully isolated. In a second study, a novel and different GFPbased selection system, in addition also involving targeted in vivo protein degradation principles,was employed for investigations of the substrate sequence space of the same protease. In two additional studies, a selection system denoted Protein Fragment Complementation Assay(PCA), based on the affinity driven structural complementation of a genetically split β-lactamase enzyme was used to identify variants having desired target protein binding abilities,including both specificity and affinity. Using Darwinian principles concerning clonal growth advantages, affibody binding proteins showing sub-nanomolar dissociation constants to thehuman cytokine TNF-α were isolated. Taken together, these studies have shown that the bacterial format is very well suited for use in various aspects of protein library selection. / QC 20100729

Diss. (sammanfattning) Umeå : Univ., 2008. / Härtill 4 uppsatser.

Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: An order picking operation in a distribution centre (DC) owned by Pep Stores Ltd, located in Durban, South Africa was considered. The order picking operation utilises picking lines and the concept of wave picking. A picking line is a central area with storage locations for pallet loads of stock keeping units (SKUs) around a conveyor belt. The system shows many similarities to unidirectional carousel systems found in literature, however, the unidirectional carousel system is not common. Sets of SKUs must be assigned to pick waves. The SKUs associated with a single wave are then arranged on a picking line after which pickers move in a clockwise direction around the conveyor belt to pick the orders. The entire order picking operation was broken into three tiers of decision making and three corresponding subproblems were identi ed. The rst two subproblems were investigated which focused on a single picking line. The rst subproblem called the order sequencing problem (OSP) considered the sequencing of orders for pickers and the second called the SKU location problem (SLP) the assignment of SKUs to locations in the picking line for a given wave. A tight lower bound was established for the OSP using the concept of a maximal cut. This lower bound was transformed into a feasible solution within 1 pick cycle of the lower bound. The solution was also shown to be robust and dynamic for use in practice. Faster solution times, however, were required for use in solution techniques for the SLP. Four variations of a greedy heuristic as well as two metaheuristic methods were therefore developed to solve the problem in shorter times. An ant colony approach was developed to solve the SLP. Furthermore, four variations of a hierarchical clustering algorithm were developed to cluster SKUs together on a picking line and three metaheuristic methods were developed to sequence these clusters. All the proposed approaches outperformed known methods for assigning locations to SKUs on a carousel. To test the validity of assumptions and assess the practicality of the proposed solutions an agent based simulation model was built. All proposed solutions were shown to be applicable in practice and the proposed solutions to both subporblems outperformed the current approaches by Pep. Furthermore, it was established that the OSP is a more important problem, in comparison to the SLP, for Pep to solve as limited savings can be achieved when solving the SLP. / AFRIKAANSE OPSOMMING: 'n Stelsel vir die opmaak van bestellings in 'n distribusiesentrum van Pep Stores Bpk. in Durban, Suid-Afrika word beskou. Hierdie stelsel gebruik uitsoeklyne waarop bestellings in golwe opgemaak word. 'n Uitsoeklyn is 'n area met vakkies waarop pallette met voorraadeenhede gestoor kan word. Hierdie vakkies is rondom 'n voerband gerangskik. Die stelsel het ooreenkomste met die eenrigting carrousselstelsels wat in die literatuur voorkom, maar hierdie eenrigtingstelsels is nie algemeen nie. Voorraadeenhede moet aan 'n golf toegewys word wat in 'n uitsoeklyn gerangskik word, waarna werkers dan die bestellings in die betrokke golf opmaak. Die hele operasie van bestellings opmaak kan opgebreek word in drie vlakke van besluite met gepaardgaande subprobleme. Die eerste twee subprobleme wat 'n enkele uitsoeklyn beskou, word aangespreek. Die eerste subprobleem, naamlik die volgorde-van-bestellings-probleem (VBP) beskou die volgorde waarin bestellings opgemaak word. Die tweede probeem is die voorraadeenheidaan- vakkie-toewysingsprobleem (VVTP) en beskou die toewysings van voorraadeenhede aan vakkies in 'n uitsoeklyn vir 'n gegewe golf. 'n Sterk ondergrens vir die VBP is bepaal met behulp van die konsep van 'n maksimum snit. Hierdie ondergrens kan gebruik word om 'n toelaatbare oplossing te bepaal wat hoogstens 1 carrousselsiklus meer as die ondergrens het. Hierdie oplossings kan dinamies gebruik word en kan dus net so in die praktyk aangewend word. Vinniger oplossingstegnieke is egter nodig indien die VVTP opgelos moet word. Twee metaheuristiese metodes word dus voorgestel waarmee oplossings vir die VBP vinniger bepaal kan word. 'n Mierkolonie benadering is ontwikkel om die VVTP op te los. Verder is vier variasies van 'n hi erargiese groeperingsalgoritme ontwikkel om voorraadeenhede saam te groepeer op 'n uitsoeklyn. Drie metaheuristieke is aangewend om hierdie groepe in volgorde te rangskik. Al hierdie benaderings vaar beter as bekende metodes om voorraadeenhede op 'n carroussel te rankskik. Om die geldigheid van die aannames en die praktiese uitvoerbaarheid van die oplossings te toets, is 'n agent gebaseerde simulasie model gebou. Daar is bevind dat al die voorgestelde oplossings prakties implementeerbaar is en dat al die metodes verbeter op die huidige werkswyse in Pep. Verder kon vasgestel word die VBP belangriker as die VVTP vir Pep is omdat veel kleiner potensiele besparings met die VVTP moontlik is as met die VBP.

CNPq / A Transgenética Computacional é uma metáfora para o desenvolvimento de algoritmos evolucionários com base na teoria de evolução endossimbiótica e em outras interações do fluxo intracelular. Diversos algoritmos foram desenvolvidos com base nesta metáfora para problemas de Otimização Combinatória, em sua maioria com um único objetivo, obtendo bons resultados. Uma vez que a consideração de mais de um objetivo leva, em geral, a representações mais realistas de problemas práticos complexos, neste trabalho investiga-se o desenvolvimento de Algoritmos Transgenéticos para problemas multiobjetivo. Tais algoritmos são examinados em versões que utilizam elementos de outros algoritmos evolucionários multiobjetivo sendo eles o NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) e o MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). Diante disso, este trabalho propõe duas novas metodologias utilizando a Transgenética Computacional acoplada ao NSGA-II e ao MOEA/D, denominadas NSTA (Non-Dominated Sorting Transgenetic Algorithm) e MOTA/D (Multi-objective Transgenetic Algorithm based on Decomposition), respectivamente. Para avaliar o desempenho das técnicas propostas, os algoritmos desenvolvidos foram aplicados a dois problemas de Otimização Combinatória, NP-difíceis,em versões com mais de um objetivo. O primeiro problema é o Caixeiro Comprador Biobjetivo e o segundo o Quadrático de Alocação multiobjetivo. Foram realizados experimentos com casos de teste disponíveis em bancos utilizados comumente por outros trabalhos da literatura. Os resultados dos algoritmos propostos foram comparados com os resultados obtidos com os algoritmos evolucionários multiobjetivo que os inspiraram. A análise dos dados obtidos com os experimentos computacionais mostram que a versão MOTA/D é a mais eficiente dentre os algoritmos do experimento com relação a qualidade da aproximação da fronteira de Pareto. / The Computational Transgenetic is a metaphor for the development of evolutionary algorithms based on the theory of evolution endosymbiotic and other intracellular interactions flow. Several algorithms have been developed based on this metaphor for combinatorial optimization problems, mostly with a single objective, obtaining good results. Once the account of more than one objective provides, in general, more realistic representations of complex practical problems, this work investigates the development of Transgenetic Algorithms for multiobjective problems. Such algorithms are examined in versions that use elements of other multiobjective evolutionary algorithms such as the NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) and the MOEA/D (Multi-objective Evolutionary Algorithm based on Decomposition). Therefore, this work proposes two new methods using Computational Transgenetic attached to NSGA-II and MOEA/D, named NSTA (Non-Dominated Sorting Transgenetic Algorithm) and MOTA/D (Multi-objective Transgenetic Algorithm based on Decomposition), respectively. To evaluate the proposed techniques performance, the experiments consider two NP-hard combinatorial optimization problems, in versions with more than one objective. The first problem is the Traveling Purchaser Problem and the second the Quadratic Assignment Problem. Experiments were performed with test cases available in benchmarks commonly used by other studies in the literature. The proposed algorithms' results were compared with those obtained by the multiobjetive evolutionary algorithms that inspired them. The analysis of data obtained by the computational experiment shows that the version MOTA/D is among the most efficient algorithms of the experiment with respect to the quality of the Pareto front approximation.