A critical set in a Latin square of order n is a set of entries in an n x n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n2-n. In Chapter 4, it is shown that lcs(n)<=n2-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders mX2^alpha (m odd, alpha>=2) and mX2^alpha+1 (m odd, alpha>=2 and alpha not equal to 3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n2 divided by 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

<p>Recent innovations in combinatorial dynamical systems permit them to be studied with algorithmic methods. One such method from topological data analysis, called persistent homology, allows one to summarize the changing homology of a sequence of simplicial complexes. This dissertation explicates three methods for capturing and summarizing changes in combinatorial dynamical systems through the lens of persistent homology. The first places the Conley index in the persistent homology setting. This permits one to capture the persistence of salient features of a combinatorial dynamical system. The second shows how to capture changes in combinatorial dynamical systems at different resolutions by computing the persistence of the Conley-Morse graph. Finally, the third places Conley's notion of continuation in the combinatorial setting and permits the tracking of isolated invariant sets across a sequence of combinatorial dynamical systems. </p>

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

<p>This work explores how randomization can be exploited to deliver sophisticated</p><p>algorithms with provable bounds for: (i) The approximation of matrix functions, such</p><p>as the log-determinant and the Von-Neumann entropy; and (ii) The low-rank approximation</p><p>of matrices. Our algorithms are inspired by recent advances in Randomized</p><p>Numerical Linear Algebra (RandNLA), an interdisciplinary research area that exploits</p><p>randomization as a computational resource to develop improved algorithms for</p><p>large-scale linear algebra problems. The main goal of this work is to encourage the</p><p>practical use of RandNLA approaches to solve Big Data bottlenecks at industrial</p><p>level. Our extensive evaluation tests are complemented by a thorough theoretical</p><p>analysis that proves the accuracy of the proposed algorithms and highlights their</p><p>scalability as the volume of data increases. Finally, the low computational time and</p><p>memory consumption, combined with simple implementation schemes that can easily</p><p>be extended in parallel and distributed environments, render our algorithms suitable</p><p>for use in the development of highly efficient real-world software.</p>

A degree-constrained subgraph construction (DCS) problem aims to find an optimal spanning subgraph (w.r.t an objective function) subject to certain degree constraints on the vertices. DCS generalizes many combinatorial optimization problems such as Matchings and Edge Covers and has many practical and real-world applications. This thesis focuses on DCS problems where there are only upper and lower bounds on the degrees, known as b-matching and b-edge cover problems, respectively. We explore linear and submodular functions as the objective functions of the subgraph construction.<br><br>The contributions of this thesis involve both the design of new approximation algorithms for these DCS problems, and also their applications to real-world contexts.<br>We designed, developed, and implemented several approximation algorithms for DCS problems. Although some of these problems can be solved exactly in polynomial time, often these algorithms are expensive, tedious to implement, and have little to no concurrency. On the contrary, many of the approximation algorithms developed here run in nearly linear time, are simple to implement, and are concurrent. Using the local dominance framework, we developed the first parallel algorithm submodular b-matching. For weighted b-edge cover, we improved the classic Greedy algorithm using the lazy evaluation technique. We also propose and analyze several approximation algorithms using the primal-dual linear programming framework and reductions to matching. We evaluate the practical performance of these algorithms through extensive experimental results.<br><br>The second contribution of the thesis is to utilize the novel algorithms in real-world applications. We employ submodular b-matching to generate a balanced task assignment for processors to build Fock matrices in the NWChemEx quantum chemistry software. Our load-balanced assignment results in a four-fold speedup per iteration of the Fock matrix computation and scales to 14,000 cores of the Summit supercomputer at Oak Ridge National Laboratory. Using approximate b-edge cover, we propose the first shared-memory and distributed-memory parallel algorithms for the adaptive anonymity problem. Minimum weighted b-edge cover and maximum weight b-matching are shown to be applicable to constructing graphs from datasets for machine learning tasks. We provide a mathematical optimization framework connecting the graph construction problem to the DCS problem.

<p>This paper aims to present a novel approach to real-time indoor temperature forecasting to meet energy consumption constraints in buildings, utilizing computing resources available at the edge of a network, close to data sources. This work was inspired by the irreversible effects of global warming accelerated by greenhouse gas emissions from burning fossil fuels. As much as human activities have heavy impacts on global energy use, it is of utmost importance to reduce the amount of energy consumed in every possible scenario where humans are involved. According to the US Environmental Protection Agency (EPA), one of the biggest greenhouse gas sources is commercial and residential buildings, which took up 13 percent of 2019 greenhouse gas emissions in the United States. In this context, it is assumed that information of the building environment such as indoor temperature and indoor humidity, and predictions based on the information can contribute to more accurate and efficient regulation of indoor heating and cooling systems. When it comes to indoor temperature, distributed IoT devices in buildings can enable more accurate temperature forecasting and eventually help to build administrators in regulating the temperature in an energy-efficient way, but without damaging the indoor environment quality. While the IoT technology shows potential as a complement to HVAC control systems, the majority of existing IoT systems integrate a remote cloud to transfer and process all data from IoT sensors. Instead, the proposed IoT system incorporates the concept of edge computing by utilizing small computer power in close proximity to sensors where the data are generated, to overcome problems of the traditional cloud-centric IoT architecture. In addition, as the microcontroller at the edge supports computing, the machine learning-based prediction of indoor temperature is performed on the microcomputer and transferred to the cloud for further processing. The machine learning algorithm used for prediction, ANN (Artificial Neural Network) is evaluated based on error metrics and compared with simple prediction models.</p>

<div>Using sensor measurements to estimate the states and parameters of a system is a fundamental task in understanding the behavior of the system. Moreover, as modern systems grow rapidly in scale and complexity, it is not always possible to deploy sensors to measure all of the states and parameters of the system, due to cost and physical constraints. Therefore, selecting an optimal subset of all the candidate sensors to deploy and gather measurements of the system is an important and challenging problem. In addition, the systems may be targeted by external attackers who attempt to remove or destroy the deployed sensors. This further motivates the formulation of resilient sensor selection strategies. In this thesis, we address the sensor selection problem under different settings as follows. </div><div><br></div><div>First, we consider the optimal sensor selection problem for linear dynamical systems with stochastic inputs, where the Kalman filter is applied based on the sensor measurements to give an estimate of the system states. The goal is to select a subset of sensors under certain budget constraints such that the trace of the steady-state error covariance of the Kalman filter with the selected sensors is minimized. We characterize the complexity of this problem by showing that the Kalman filtering sensor selection problem is NP-hard and cannot be approximated within any constant factor in polynomial time for general systems. We then consider the optimal sensor attack problem for Kalman filtering. The Kalman filtering sensor attack problem is to attack a subset of selected sensors under certain budget constraints in order to maximize the trace of the steady-state error covariance of the Kalman filter with sensors after the attack. We show that the same results as the Kalman filtering sensor selection problem also hold for the Kalman filtering sensor attack problem. Having shown that the general sensor selection and sensor attack problems for Kalman filtering are hard to solve, our next step is to consider special classes of the general problems. Specifically, we consider the underlying directed network corresponding to a linear dynamical system and investigate the case when there is a single node of the network that is affected by a stochastic input. In this setting, we show that the corresponding sensor selection and sensor attack problems for Kalman filtering can be solved in polynomial time. We further study the resilient sensor selection problem for Kalman filtering, where the problem is to find a sensor selection strategy under sensor selection budget constraints such that the trace of the steady-state error covariance of the Kalman filter is minimized after an adversary removes some of the deployed sensors. We show that the resilient sensor selection problem for Kalman filtering is NP-hard, and provide a pseudo-polynomial-time algorithm to solve it optimally.</div><div> </div><div> Next, we consider the sensor selection problem for binary hypothesis testing. The problem is to select a subset of sensors under certain budget constraints such that a certain metric of the Neyman-Pearson (resp., Bayesian) detector corresponding to the selected sensors is optimized. We show that this problem is NP-hard if the objective is to minimize the miss probability (resp., error probability) of the Neyman-Pearson (resp., Bayesian) detector. We then consider three optimization objectives based on the Kullback-Leibler distance, J-Divergence and Bhattacharyya distance, respectively, in the hypothesis testing sensor selection problem, and provide performance bounds on greedy algorithms when applied to the sensor selection problem associated with these optimization objectives.</div><div> </div><div> Moving beyond the binary hypothesis setting, we also consider the setting where the true state of the world comes from a set that can have cardinality greater than two. A Bayesian approach is then used to learn the true state of the world based on the data streams provided by the data sources. We formulate the Bayesian learning data source selection problem under this setting, where the goal is to minimize the cost spent on the data sources such that the learning error is within a certain range. We show that the Bayesian learning data source selection is also NP-hard, and provide greedy algorithms with performance guarantees.</div><div> </div><div> Finally, in light of the COVID-19 pandemic, we study the parameter estimation measurement selection problem for epidemics spreading in networks. Here, the measurements (with certain costs) are collected by conducting virus and antibody tests on the individuals in the epidemic spread network. The goal of the problem is then to optimally estimate the parameters (i.e., the infection rate and the recovery rate of the virus) in the epidemic spread network, while satisfying the budget constraint on collecting the measurements. Again, we show that the measurement selection problem is NP-hard, and provide approximation algorithms with performance guarantees.</div>

<p>Klaster analiza ima dugu istoriju i mada se<br />primenjuje u mnogim oblastima i dalje ostaju<br />značajni izazovi. U disertaciji je prikazan uvod<br />u neglatki optimizacioni pristup u<br />klasterovanju, sa osvrtom na problem<br />klasterovanja velikih skupova podataka.<br />Međutim, ovi optimizacioni algoritmi bolje<br />funkcioni&scaron;u u radu sa neprekidnim podacima.<br />Jedan od glavnih izazova u klaster analizi je<br />rad sa velikim skupovima podataka sa<br />kategorijalnim i kombinovanim (numerički i<br />kategorijalni) tipovima promenljivih. Rad sa<br />velikim brojem instanci (objekata) i velikim<br />brojem dimenzija (promenljivih), može<br />predstavljati problem u klaster analizi, zbog<br />vremenske složenosti. Jedan od načina<br />re&scaron;avanja ovog problema je redukovanje broja<br />instanci, bez gubitka informacija.<br />Prvi cilj disertacije je bio upoređivanje<br />rezultata klasterovanja na celom skupu i<br />prostim slučajnim uzorcima sa kategorijalnim i<br />kombinovanim podacima, za različite veličine<br />uzorka i različit broj klastera. Nije utvrđena<br />značajna razlika (p&gt;0.05) u rezultatima<br />klasterovanja na uzorcima obima<br />0.03m,0.05m,0.1m,0.3m (gde je m obim<br />posmatranog skupa) i celom skupu.<br />Drugi cilj disertacije je bio konstrukcija<br />efikasnog postupka klasterovanja velikih<br />skupova podataka sa kategorijalnim i<br />kombinovanim tipovima promenljivih.<br />Predloženi postupak se sastoji iz sledećih<br />koraka: 1. klasterovanje na prostim slučajnim<br />uzorcima određene kardinalnosti; 2.<br />određivanje najboljeg klasterskog re&scaron;enja na<br />uzorku, primenom odgovarajućeg kriterijuma<br />validnosti; 3. dobijeni centri klastera iz ovog<br />uzorka služe za klasterovanje ostatka skupa.<br />Treći cilj disertacije predstavlja primenu<br />klaster analize u definisanju klastera<br />bihejvioralnih faktora rizika u populaciji<br />odraslog stanovni&scaron;tva Srbije, kao i analizu<br />sociodemografskih karakteristika dobijenih<br />klastera. Klaster analiza je primenjena na<br />velikom reprezentativnom uzorku odraslog<br />stanovni&scaron;tva Srbije, starosti 20 i vi&scaron;e godina.<br />Izdvojeno je pet jasno odvojenih klastera sa<br />karakterističnim kombinacijama bihejvioralnih<br />faktora rizika: Bez rizičnih faktora, &Scaron;tetna<br />upotreba alkohola i druge rizične navike,<br />Nepravilna ishrana i druge rizične navike,<br />Nedovoljna fizička aktivnost, Pu&scaron;enje. Rezultati<br />multinomnog logističkog regresionog modela<br />ukazuju da ispitanici koji nisu u braku, lo&scaron;ijeg<br />su materijalnog stanja, nižeg obrazovanja i žive<br />u Vojvodini imaju veću &scaron;ansu za prisustvo<br />vi&scaron;estrukih bihejvioralnih faktora rizika.</p> / <p>The cluster analysis has a long history and a<br />large number of clustering techniques have<br />been developed in many areas, however,<br />significant challenges still remain. In this<br />thesis we have provided a introduction to<br />nonsmooth optimization approach to clustering<br />with reference to clustering large datasets.<br />Nevertheless, these optimization clustering<br />algorithms work much better when a dataset<br />contains only vectors with continuous features.<br />One of the main challenges is clustering of large<br />datasets with categorical and mixed (numerical<br />and categorical) data. Clustering deals with a<br />large number of instances (objects) and a large<br />number of dimensions (variables) can be<br />problematic because of time complexity. One of<br />the ways to solve this problem is by reducing<br />the number of instances, without the loss of<br />information.<br />The first aim of this thesis was to compare<br />the results of cluster algorithms on the whole<br />dataset and on simple random samples with<br />categorical and mixed data, in terms of validity,<br />for different number of clusters and for<br />different sample sizes. There were no<br />significant differences (p&gt;0.05) between the<br />obtained results on the samples of the size of<br />0.03m,0.05m,0.1m,0.3m (where m is the size of<br />the dataset) and the whole dataset.<br />The second aim of this thesis was to<br />develop an efficient clustering procedure for<br />large datasets with categorical and mixed<br />(numeric and categorical) values. The proposed<br />procedure consists of the following steps: 1.<br />clustering on simple random samples of a given<br />cardinality; 2. finding the best cluster solution<br />on a sample (by appropriate validity measure);<br />3. using cluster centers from this sample for<br />clustering of the remaining data.<br />The third aim of this thesis was to<br />examine clustering of four lifestyle risk factors<br />and to examine the variation across different<br />socio-demographic groups in a Serbian adult<br />population. Cluster analysis was carried out on<br />a large representative sample of Serbian adults<br />aged 20 and over. We identified five<br />homogenous health behaviour clusters with<br />specific combination of risk factors: &#39;No Risk<br />Behaviours&#39;, &#39;Drinkers with Risk Behaviours&#39;,<br />&#39;Unhealthy diet with Risk Behaviours&#39;,<br />&#39;Smoking&#39;. Results of multinomial logistic<br />regression indicated that single adults, less<br />educated, with low socio-economic status and<br />living in the region of Vojvodina are most likely<br />to be a part of the clusters with a high-risk<br />profile.</p>