Theory and Algorithms Commons^™

Vertex Coloring With Forbidden Subgraphs, Yingjun Dai

Theses and Dissertations (Comprehensive)

Given a set $L$ of graphs, a graph $G$ is $L$-free if $G$ does not contain any graph in $L$ as induced subgraph. A $hole$ is an induced cycle of length at least $4$. A $hole$-$twin$ is a graph obtained by adding a vertex adjacent to three consecutive vertices in a $hole$. Hole-twins are closely related to the characterization of the line graphs in terms of forbidden subgraphs.

By using {\it clique-width} and {\it perfect graphs} theory, we show that ($claw$,$4K_1$,$hole$-$twin$)-free graphs and ($4K_1$,$hole$-$twin$,$5$-$wheel$)-free graphs are either perfect or have bounded clique-width. And thus the coloring of them can be …

Quantifying Human Biological Age: A Machine Learning Approach, Syed Ashiqur Rahman

Graduate Theses, Dissertations, and Problem Reports (ETD)

Quantifying human biological age is an important and difficult challenge. Different biomarkers and numerous approaches have been studied for biological age prediction, each with its advantages and limitations. In this work, we first introduce a new anthropometric measure (called Surface-based Body Shape Index, SBSI) that accounts for both body shape and body size, and evaluate its performance as a predictor of all-cause mortality. We analyzed data from the National Health and Human Nutrition Examination Survey (NHANES). Based on the analysis, we introduce a new body shape index constructed from four important anthropometric determinants of body shape and body size: body …

Pharmaceutical Scheduling Using Simulated Annealing And Steepest Descent Method, Bryant Jamison Spencer

Graduate Theses, Dissertations, and Problem Reports (ETD)

In the pharmaceutical manufacturing world, a deadline could be the difference between losing a multimillion-dollar contract or extending it. This, among many other reasons, is why good scheduling methods are vital. This problem report addresses Flexible Flowshop (FF) scheduling using Simulated Annealing (SA) in conjunction with the Steepest Descent heuristic (SD).

FF is a generalized version of the flowshop problem, where each product goes through S number of stages, where each stage has M number of machines. As opposed to a normal flowshop problem, all ‘jobs’ do not have to flow in the same sequence from stage to stage. The …

Reinforcement Learning For Collective Multi-Agent Decision Making, Duc Thien Nguyen

Dissertations and Theses Collection (Open Access)

In this thesis, we study reinforcement learning algorithms to collectively optimize decentralized policy in a large population of autonomous agents. We notice one of the main bottlenecks in large multi-agent system is the size of the joint trajectory of agents which quickly increases with the number of participating agents. Furthermore, the noiseof actions concurrently executed by different agents in a large system makes it difficult for each agent to estimate the value of its own actions, which is well-known as the multi-agent credit assignment problem. We propose a compact representation for multi-agent systems using the aggregate counts to address …

Data Center Holistic Demand Response Algorithm To Smooth Microgrid Tie-Line Power Fluctuation, Ting Yang, Yingjie Zhao, Haibo Pen, Zhaoxia Wang

Research Collection School Of Computing and Information Systems

With the rapid development of cloud computing, artificial intelligence technologies and big data applications, data centers have become widely deployed. High density IT equipment in data centers consumes a lot of electrical power, and makes data center a hungry monster of energy consumption. To solve this problem, renewable energy is increasingly integrated into data center power provisioning systems. Compared to the traditional power supply methods, renewable energy has its unique characteristics, such as intermittency and randomness. When renewable energy supplies power to the data center industrial park, this kind of power supply not only has negative effects on the normal …

Efficient Stochastic Gradient Hard Thresholding, Pan Zhou, Xiao-Tong Yuan, Jiashi Feng

Research Collection School Of Computing and Information Systems

Stochastic gradient hard thresholding methods have recently been shown to work favorably in solving large-scale empirical risk minimization problems under sparsity or rank constraint. Despite the improved iteration complexity over full gradient methods, the gradient evaluation and hard thresholding complexity of the existing stochastic algorithms usually scales linearly with data size, which could still be expensive when data is huge and the hard thresholding step could be as expensive as singular value decomposition in rank-constrained problems. To address these deficiencies, we propose an efficient hybrid stochastic gradient hard thresholding (HSG-HT) method that can be provably shown to have sample-size-independent gradient …

Sequence Pattern Mining With Variables, James S. Okolica, Gilbert L. Peterson, Robert F. Mills, Michael R. Grimaila

Faculty Publications

Sequence pattern mining (SPM) seeks to find multiple items that commonly occur together in a specific order. One common assumption is that all of the relevant differences between items are captured through creating distinct items, e.g., if color matters then the same item in two different colors would have two items created, one for each color. In some domains, that is unrealistic. This paper makes two contributions. The first extends SPM algorithms to allow item differentiation through attribute variables for domains with large numbers of items, e.g, by having one item with a variable with a color attribute rather than …

Constrained K-Means Clustering Validation Study, Nicholas Mcdaniel, Stephen Burgess, Jeremy Evert

Student Research

Machine Learning (ML) is a growing topic within Computer Science with applications in many fields. One open problem in ML is data separation, or data clustering. Our project is a validation study of, “Constrained K-means Clustering with Background Knowledge" by Wagstaff et. al. Our data validates the finding by Wagstaff et. al., which shows that a modified k-means clustering approach can outperform more general unsupervised learning algorithms when some domain information about the problem is available. Our data suggests that k-means clustering augmented with domain information can be a time efficient means for segmenting data sets. Our validation study focused …

Criticality Assessments For Improving Algorithmic Robustness, Thomas B. Jones

Computer Science ETDs

Though computational models typically assume all program steps execute flawlessly, that does not imply all steps are equally important if a failure should occur. In the "Constrained Reliability Allocation" problem, sufficient resources are guaranteed for operations that prompt eventual program termination on failure, but those operations that only cause output errors are given a limited budget of some vital resource, insufficient to ensure correct operation for each of them.

In this dissertation, I present a novel representation of failures based on a combination of their timing and location combined with criticality assessments---a method used to predict the behavior of systems …

A Multi-Task Approach To Incremental Dialogue State Tracking, Anh Duong Trinh, Robert J. Ross, John D. Kelleher

Conference papers

Incrementality is a fundamental feature of language in real world use. To this point, however, the vast majority of work in automated dialogue processing has focused on language as turn based. In this paper we explore the challenge of incremental dialogue state tracking through the development and analysis of a multi-task approach to incremental dialogue state tracking. We present the design of our incremental dialogue state tracker in detail and provide evaluation against the well known Dialogue State Tracking Challenge 2 (DSTC2) dataset. In addition to a standard evaluation of the tracker, we also provide an analysis of the Incrementality …

Genetic Algorithm Design Of Photonic Crystals For Energy-Efficient Ultrafast Laser Transmitters, Troy A. Hutchins-Delgado

Shared Knowledge Conference

Photonic crystals allow light to be controlled and manipulated such that novel photonic devices can be created. We are interested in using photonic crystals to increase the energy efficiency of our semiconductor whistle-geometry ring lasers. A photonic crystal will enable us to reduce the ring size, while maintaining confinement, thereby reducing its operating power. Photonic crystals can also exhibit slow light that will increase the interaction with the material. This will increase the gain, and therefore, lower the threshold for lasing to occur. Designing a photonic crystal for a particular application can be a challenge due to its number of …

Sampling Complexity Of Bosonic Random Walkers On A One-Dimensional Lattice, Gopikrishnan Muraleedharan, Akimasa Miyake, Ivan Deutsch

Shared Knowledge Conference

Computers based quantum logic are believed to solve problems faster and more efficiently than computers based on classical boolean logic. However, a large-scale universal quantum computer with error correction may not be realized in near future. But we can ask the question: can we devise a specific problem that a quantum device can solve faster than current state of the art super computers? One such problem is the so called "Boson Sampling" problem introduced by Aaronson and Arkhipov. The problem is to generate random numbers according to same distribution as the output number configurations of photons in linear optics. It …

Using Finite-State Models For Log Differencing, Hen Amar, Lingfeng Bao, Nimrod Busany, David Lo, Shahar Maoz

Research Collection School Of Computing and Information Systems

Much work has been published on extracting various kinds of models from logs that document the execution of running systems. In many cases, however, for example in the context of evolution, testing, or malware analysis, engineers are interested not only in a single log but in a set of several logs, each of which originated from a different set of runs of the system at hand. Then, the difference between the logs is the main target of interest. In this work we investigate the use of finite-state models for log differencing. Rather than comparing the logs directly, we generate concise …

Differentially Private Location Protection With Continuous Time Stamps For Vanets, Zhili Chen, Xianyue Bao, Zuobin Ying, Ximeng Liu, Hong Zhong

Research Collection School Of Computing and Information Systems

Vehicular Ad hoc Networks (VANETs) have higher requirements of continuous Location-Based Services (LBSs). However, the untrusted server could reveal the users’ location privacy in the meantime. Syntactic-based privacy models have been widely used in most of the existing location privacy protection schemes. Whereas, they are suffering from background knowledge attacks, neither do they take the continuous time stamps into account. Therefore we propose a new differential privacy definition in the context of location protection for the VANETs, and we designed an obfuscation mechanism so that fine-grained locations and trajectories will not exposed when vehicles request location-based services on continuous time …

Unsupervised User Identity Linkage Via Factoid Embedding, Wei Xie, Xin Mu, Roy Ka Wei Lee, Feida Zhu, Ee-Peng Lim

Research Collection School Of Computing and Information Systems

User identity linkage (UIL), the problem of matching user account across multiple online social networks (OSNs), is widely studied and important to many real-world applications. Most existing UIL solutions adopt a supervised or semisupervised approach which generally suffer from scarcity of labeled data. In this paper, we propose Factoid Embedding, a novel framework that adopts an unsupervised approach. It is designed to cope with different profile attributes, content types and network links of different OSNs. The key idea is that each piece of information about a user identity describes the real identity owner, and thus distinguishes the owner from other …

On The Sequential Massart Algorithm For Statistical Model Checking, Cyrille Jegourel, Jun Sun, Jin Song Dong

Research Collection School Of Computing and Information Systems

Several schemes have been provided in Statistical Model Checking (SMC) for the estimation of property occurrence based on predefined confidence and absolute or relative error. Simulations might be however costly if many samples are required and the usual algorithms implemented in statistical model checkers tend to be conservative. Bayesian and rare event techniques can be used to reduce the sample size but they can not be applied without prerequisite or knowledge about the system under scrutiny. Recently, sequential algorithms based on Monte Carlo estimations and Massart bounds have been proposed to reduce the sample size while providing guarantees on error …

Exploring The Effect Of Different Numbers Of Convolutional Filters And Training Loops On The Performance Of Alphazero, Jared Prince

Masters Theses & Specialist Projects

In this work, the algorithm used by AlphaZero is adapted for dots and boxes, a two-player game. This algorithm is explored using different numbers of convolutional filters and training loops, in order to better understand the effect these parameters have on the learning of the player. Different board sizes are also tested to compare these parameters in relation to game complexity. AlphaZero originated as a Go player using an algorithm which combines Monte Carlo tree search and convolutional neural networks. This novel approach, integrating a reinforcement learning method previously applied to Go (MCTS) with a supervised learning method (neural networks) …

Influence Maximization On Social Graphs: A Survey, Yuchen Li, Ju Fan, Yanhao Wang, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

Influence Maximization (IM), which selects a set of k users (called seed set) from a social network to maximize the expected number of influenced users (called influence spread), is a key algorithmic problem in social influence analysis. Due to its immense application potential and enormous technical challenges, IM has been extensively studied in the past decade. In this paper, we survey and synthesize a wide spectrum of existing studies on IM from an algorithmic perspective, with a special focus on the following key aspects (1) a review of well-accepted diffusion models that capture information diffusion process and build the foundation …

The Chapman Bone Algorithm: A Diagnostic Alternative For The Evaluation Of Osteoporosis, Elise Levesque, Anton Ketterer, Wajiha Memon, Cameron James, Noah Barrett, Cyril Rakovski, Frank Frisch

Mathematics, Physics, and Computer Science Faculty Articles and Research

Osteoporosis is the most common metabolic bone disease and goes largely undiagnosed throughout the world, due to the inaccessibility of DXA machines. Multivariate analyses of serum bone turnover markers were evaluated in 226 Orange County, California, residents with the intent to determine if serum osteocalcin and serum pyridinoline cross-links could be used to detect the onset of osteoporosis as effectively as a DXA scan. Descriptive analyses of the demographic and lab characteristics of the participants were performed through frequency, means and standard deviation estimations. We implemented logistic regression modeling to find the best classification algorithm for osteoporosis. All calculations and …

An Outlier Detection Algorithm Based On Cross-Correlation Analysis For Time Series Dataset, Hui Lu, Yaxian Liu, Zongming Fei, Chongchong Guan

Computer Science Faculty Publications

Outlier detection is a very essential problem in a variety of application areas. Many detection methods are deficient for high-dimensional time series data sets containing both isolated and assembled outliers. In this paper, we propose an Outlier Detection method based on Cross-correlation Analysis (ODCA). ODCA consists of three key parts. They are data preprocessing, outlier analysis, and outlier rank. First, we investigate a linear interpolation method to convert assembled outliers into isolated ones. Second, a detection mechanism based on the cross-correlation analysis is proposed for translating the high-dimensional data sets into 1-D cross-correlation function, according to which the isolated outlier …