Cut problems on graphs are a well-known and intensively studied class of optimization problems. In this thesis, we study the maximum cut problem, the maximum bond problem, and the minimum multicut problem through their associated polyhedra, i.e., the cut polytope, the bond polytope, and the multicut dominant, respectively. Continuing the research on the maximum cut problem and the cut polytope, we present a linear description for cut polytopes of K_{3,3}-minor-free graphs as well as an algorithm solving the maximum cut problem on these graphs in the same running time as planar maximum cut. Moreover, we give a complete characterization of simple and simplicial cut polytopes. Considering the maximum cut problem from an algorithmic point of view, we propose an FPT-algorithm for the maximum cut problem parameterized by the crossing number. We start the structural study of the bond polytope by investigating its basic properties and the effect of graph operations on the bond polytope and its facet-defining inequalities. After presenting a linear-time reduction of the maximum bond problem to the maximum bond problem on 3-connected graphs, we discuss valid and facet defining inequalities arising from edges and cycles. These inequalities yield a complete linear description for bond polytopes of 3-connected planar (K_5-e)-minor-free graphs. This polytopal result is mirrored algorithmically by proposing a linear-time algorithm for the maximum bond problem on (K_5-e)-minor-free graphs. Finally, we start the structural study of the multicut dominant. We investigate basic properties, which gives rise to lifting and projection results for the multicut dominant. Then, we study the effect of graph operations on the multicut dominant and its facet-defining inequalities. Moreover, we present facet-defining inequalities supported on stars, trees, and cycles as well as separation algorithms for the former two classes of inequalities.

This is a project with the ambition of demonstrating the possibilities and applications of the quantum approximation optimization algorithm (QAOA). Throughout the paper discussions on the theoretical background and fundamentals of the algorithm will be done by examining the relevant nomenclature. Then a set of possible application problems will be considered where it will be discussed why this specific algorithm is of interest for each individual problem. In the fourth section these problems will concretely be tested via simulations of the QAOA and lastly an analysis of the outcomes will be done.

In this thesis, we study the intersection of optimization and machine learning, especially how to use machine learning and optimization tools to make decisions. In Chapter 1, we propose a novel approach for accurate policy evaluation in personalized pricing. We solve an optimization problem to evaluate new pricing strategies, while searching over some worst case revenue functions. In Chapter 2, we consider problems where parameters are predicted using a machine learning model to be used for downstream optimization tasks. Recent works have proposed an integrated approach, accounting for how predictions are used in the downstream optimization problem, instead of just minimizing prediction error. We analyze the asymptotic performance of methods under the integrated and traditional approaches, in the sense of first-order stochastic. We argue that when the model class is rich enough to cover the ground truth, the traditional predict-then-optimize approach outperforms the integrated approach, and the performance ordering between the two approaches is reversed when the model is misspecified. In Chapter 3, we present a new class of architectures for reinforcement learning, Implicit Two-Tower (ITT) policies, where the actions are chosen based on the attention scores of their learnable latent representations with those of the input states. We show that ITT-architectures are particularly suited for evolutionary optimization and the corresponding policy training algorithms outperform their vanilla unstructured implicit counterparts as well as commonly used explicit policies. In Chapter 4, we consider an active learning problem, in which the learner has the ability to sequentially select unlabeled samples for labeling. A typical active learning algorithm would sample more points at “difficult" regions in the feature space to more efficiently use the sampling budget and reduce excess risk. For nonparametric classification with smooth regression functions, we show that nuances in notions of margin that involves the uniqueness of the Bayes classifier, having no apparent effect on rates in passive learning, determine whether or not any active learner can outperform passive learning rates.

京都大学 / 新制・課程博士 / 博士(工学) / 甲第24581号 / 工博第5087号 / 新制||工||1974(附属図書館) / 京都大学大学院工学研究科材料工学専攻 / (主査)教授 田中 功, 教授 安田 秀幸, 教授 中村 裕之 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all trees with diameter four. We also give the maximum number of pegs that can be left on such a graph under the restriction that we jump whenever possible.

<p>Real-world datasets are rarely clean. This causes the discrepancy between the claimed performance of machine learning algorithms on paper, and their actual performance on real-world problems. When dealing with missing or hidden information in a dataset, researchers have been using heuristic imputation methods since the first day of machine learning. However, it is known that many imputation methods do not have theoretical guarantees in various machine learning tasks, including clustering, community detection, sparsity recovery, to name a few. On the other hand, theoretical machine learning papers often follow simplistic assumptions, which are rarely fulfilled in real-world datasets. My research focuses on developing statistically and computationally efficient learning algorithms with provable guarantees under novel incomplete and latent assumptions. We consider problems with arguably more realistic incomplete and latent assumptions.We provide analysis to community detection in various network models, inference with latent variables in an arbitrary planted model, federated myopic community detection, and high-order tensor models. We analyze the interaction between the missing or latent structures and the inference / recoverability conditions, and proposed algorithms to solve the problems efficiently. <br> <br> Our main contributions in this thesis are as follows.<br> </p> <ol> <li>We analyze the information-theoretic limits for the recovery of node labels in several network models. We analyze the information-theoretic limits for community detection. We carefully construct restricted ensembles for a subclass of network models, and provide a series of novel results. </li> <li>We analyze the necessary and sufficient conditions for exact inference of a latent model. We show that exact inference can be achieved using a semidefinite programming approach without knowing either the latent variables or their domain. Our analysis predicts the experimental correctness of SDP with high accuracy, showing the suitability of our focus on the Karush-Kuhn-Tucker conditions and the spectrum of a properly defined matrix.</li> <li>We study the problem of recovering the community structure of a network under federated myopic learning. Under this paradigm, we have several clients, each of them having a myopic view, i.e., observing a small subgraph of the network. Each client sends a censored evidence graph to a central server. We provide an efficient algorithm, which computes a consensus signed weighted graph from clients evidence, and recovers the underlying network structure in the central server. We analyze the topological structure conditions of the network, as well as the signal and noise levels of the clients that allow for recovery of the network structure. Our analysis shows that exact recovery is possible and can be achieved in polynomial time.</li> <li>We study the problem of exact partitioning of high-order models. We consider two different high-order assumptions, and show that exact partitioning of high-order planted models is achievable through solving a convex optimization problem with a novel Carathéodory symmetric tensor cone in one case, and with a tensor nuclear norm constraint in the other.</li> <li>We study the problem of inference in high-order structured prediction tasks. We apply a generative model approach to study the problem of high-order inference, and provide a two-stage convex optimization algorithm for exact label recovery. We also connect the performance of our algorithm and the hyperedge expansion property using a novel hypergraph Cheeger-type inequality.</li> <li>We study the problem of partial recovery through semidefinite programming. We are interested in the scenarios in which the SDP returns a solution that is partially correct without any rounding. We analyze the optimality condition of partial recovery and provide statistical and topological guarantees. </li> </ol>

The main goal of a scheduling process is to decide when and how to execute each of the project’s activities. Despite large variety of researched scheduling problems, the majority of them can be described as generalisations of the resource-constrained project scheduling problem (RCPSP). Because of wide applicability and challenging difficulty, RCPSP has attracted vast amount of attention in the research community and great variety of heuristics have been adapted for solving it. Even though these heuristics are structurally different and operate according to diverse principles, they are designed to obtain only one solution at a time. In the recent researches on RCPSPs, it was proven that these kind of problems have complex multimodal fitness landscapes, which are characterised by a wide solution search spaces and presence of multiple local and global optima. The main goal of this thesis is twofold. Firstly, it presents a variation of the RCPSP that considers optimisation of projects in an uncertain environment where resources are modelled to adapt to their environment and, as the result of this, improve their efficiency. Secondly, modification of a novel evolutionary computation method Cuckoo Search (CS) is proposed, which has been adapted for solving combinatorial optimisation problems and modified to obtain multiple solutions. To test the proposed methodology, two sets of experiments are carried out. Firstly, the developed algorithm is applied to a real-life software development project. Secondly, the performance of the algorithm is tested on universal benchmark instances for scheduling problems which were modified to take into account specifics of the proposed optimisation model. The results of both experiments demonstrate that the proposed methodology achieves competitive level of performance and is capable of finding multiple global solutions, as well as prove its applicability in real-life projects.

Worst-case analysis (WCA) has been the dominant tool for understanding the performance of the lion share of algorithmic arsenal of theoretical computer science. While WCA has provided us a thorough picture for a variety of problems over the last few decades, the advent of Machine Learn- ing era renewed our interest in several important optimization problems whose actual complexity have been elusive for empirical and real-world instances. More interestingly, while state-of-the- art ML models become deeper, larger in scale, sequential and highly nonconvex, the backbone of modern learning algorithms are simple algorithms such as Local Search, Gradient Descent and Follow The Leader variations (in the case of multi-agent tasks). Thus, a basic question endures: Why do simple algorithms work so well even in these challenging settings? A rapidly developing recent line of research, the so-called beyond worst-case analysis of algo- rithms (BWCA), aims to bridge this gap between theory and practice considering the design and analysis of algorithms using more realistic models or using natural structural properties. In this the- sis, we continue the line of work of BWCA by making contributions in several areas. Specifically, we focus on four main problems and models: 1. In combinatorial optimization, can simple flip local search methods compute local optima efficiently? 2. In continuous optimization, are the gradients necessary to compute efficiently local optima in the general nonconvex setting? 3. In multi-agent optimization, what is the computational complexity of generalized Nash Equi- libria and how simple dynamics behave on them? 4. In the special case of nonconvex-nonconcave minmax optimization, are there rich classes of ML well-motivated games with an effectively unique game theoretic solution that is selected by standard optimization techniques (e.g gradient descent) ? Leveraging machinery like the celebrated Smoothed Analysis of Spielman and Tang and the widely studied Lyapunov’s Stability Analysis, in this thesis we show that although the standard versions of these classical algorithms do not enjoy good theoretical properties in the worst case, simple modifications are sufficient to grant them desirable behaviors, which explain the underlying mechanisms behind their favorable performance in practice.

[pt] Compreensão de dados, codificação digital da fala, telecomunicações via celular, correção de erros de transmissão, são algumas das aplicações práticas do estudo dos códigos de cobertura, um importante ramo da área da matemática denominada teoria dos códigos. Neste trabalho são abordados dois problemas de códigos de cobertura: o problema clássico de códigos de cobertura e o recente problema denominado de códigos curtos de cobertura. Apresenta-se uma aplicação da metaeurística Busca Tabu Reativa, uma importante variação da Busca Tabu clássica, para os problemas citados. Além disto, apresenta-se uma nova técnica heurística para resolução de problemas de otimização combinatória denominada Heurística de Melhoria via Geração de Colunas (HMGC), juntamente com uma aplicação da mesma aos problemas em questão. A HMGC combina a geração atrasada de colunas, técnica usada na resolução de problemas com um grande número de variáveis de decisão (colunas), e heurísticas de busca local. É feita uma comparação dos resultados obtidos pela Busca Tabu Reativa, a Busca Tabu sem o mecanismo de reação e a HMGC, de forma a avaliar a qualidade das heurísticas apresentadas. / [en] Data compression, speech coding, móbile telecommunications and error-corretion are some of the practical apllications of the covering codes study, an important field of coding theory. This work addresses two problems of covering codes: the classic code covering problem and the recent short code covering problem. It presents an application of Reactive Tabu Search (RTS) metaheuristic for the problems cited, the RTS is an important variation of the classic Tabu Search. Moreover, it presents a new heuristic technique for solving combinatorial optimization problems named Column Generation Improbement Heuristic (CGIH). It also presents an application of CGIH for the covering codes problems. The CGIH combines the delayed column generation, technique used to solve problems with a large number of decision variables (columns), and local search heuristics. A comparison of results obtained by the Reactive Tabu Search, the Tabu Search without the reaction mechanism and the CGIH is also presented in order to assess the effectivenss of the presented heuristics.

The completion of the human genome project in 2003 paved the way for studies to better understand and catalog variation in the human genome. The International HapMap Project was started in 2002 with the aim of identifying genetic variation in the human genome and studying the distribution of genetic variation across populations of individuals. The information collected by the HapMap project will enable researchers in associating genetic variations with phenotypic variations. Single Nucleotide Polymorphisms (SNPs) are loci in the genome where two individuals differ in a single base. It is estimated that there are approximately ten million SNPs in the human genome. These ten million SNPS are not completely independent of each other - blocks (contiguous regions) of neighboring SNPs on the same chromosome are inherited together. The pattern of SNPs on a block of the chromosome is called a haplotype. Each block might contain a large number of SNPs, but a small subset of these SNPs are sufficient to uniquely dentify each haplotype in the block. The haplotype map or HapMap is a map of these haplotype blocks. Haplotypes, rather than individual SNP alleles are expected to effect a disease phenotype. The human genome is diploid, meaning that in each cell there are two copies of each chromosome - i.e., each individual has two haplotypes in any region of the chromosome. With the current technology, the cost associated with empirically collecting haplotype data is prohibitively expensive. Therefore, the un-ordered bi-allelic genotype data is collected experimentally. The genotype data gives the two alleles in each SNP locus in an individual, but does not give information about which allele is on which copy of the chromosome. This necessitates computational techniques for inferring haplotypes from genotype data. This computational problem is called the haplotype inference problem. Many statistical approaches have been developed for the haplotype inference problem. Some of these statistical methods have been shown to be reasonably accurate on real genotype data. However, these techniques are very computation-intensive. With the international HapMap project collecting information from nearly 10 million SNPs, and with association studies involving thousands of individuals being undertaken, there is a need for more efficient methods for haplotype inference. This dissertation is an effort to develop efficient perfect phylogeny based combinatorial algorithms for haplotype inference. The perfect phylogeny haplotyping (PPH) problem is to derive a set of haplotypes for a given set of genotypes with the condition that the haplotypes describe a perfect phylogeny. The perfect phylogeny approach to haplotype inference is applicable to the human genome due to the block structure of the human genome. An important contribution of this dissertation is an optimal O(nm) time algorithm for the PPH problem, where n is the number of genotypes and m is the number of SNPs involved. The complexity of the earlier algorithms for this problem was O(nm^2). The O(nm) complexity was achieved by applying some transformations on the input data and by making use of the FlexTree data structure that has been developed as part of this dissertation work, which represents all the possible PPH solution for a given set of genotypes. Real genotype data does not always admit a perfect phylogeny, even within a block of the human genome. Therefore, it is necessary to extend the perfect phylogeny approach to accommodate deviations from perfect phylogeny. Deviations from perfect phylogeny might occur because of recombination events and repeated or back mutations (also referred to as homoplasy events). Another contribution of this dissertation is a set of fixed-parameter tractable algorithms for constructing near-perfect phylogenies with homoplasy events. For the problem of constructing a near perfect phylogeny with q homoplasy events, the algorithm presented here takes O(nm^2+m^(n+m)) time. Empirical analysis on simulated data shows that this algorithm produces more accurate results than PHASE (a popular haplotype inference program), while being approximately 1000 times faster than phase. Another important problem while dealing real genotype or haplotype data is the presence of missing entries. The Incomplete Perfect Phylogeny (IPP) problem is to construct a perfect phylogeny on a set of haplotypes with missing entries. The Incomplete Perfect Phylogeny Haplotyping (IPPH) problem is to construct a perfect phylogeny on a set of genotypes with missing entries. Both the IPP and IPPH problems have been shown to be NP-hard. The earlier approaches for both of these problems dealt with restricted versions of the problem, where the root is either available or can be trivially re-constructed from the data, or certain assumptions were made about the data. We make some novel observations about these problems, and present efficient algorithms for unrestricted versions of these problems. The algorithms have worst-case exponential time complexity, but have been shown to be very fast on practical instances of the problem.