Theory and Algorithms Commons^™

Promoting Diversity In Academic Research Communities Through Multivariate Expert Recommendation, Omar Salman

Graduate Theses and Dissertations

Expert recommendation is the process of identifying individuals who have the appropriate knowledge and skills to achieve a specific task. It has been widely used in the educational environment mainly in the hiring process, paper-reviewer assignment, and assembling conference program committees. In this research, we highlight the problem of diversity and fair representation of underrepresented groups in expertise recommendation, factors that current expertise recommendation systems rarely consider. We introduce a novel way to model experts in academia by considering demographic attributes in addition to skills. We use the h-index score to quantify skills for a researcher and we identify five …

An Adaptive Large Neighborhood Search For The Green Mixed Fleet Vehicle Routing Problem With Realistic Energy Consumption And Partial Recharges, Vincent F. Yu, Panca Jodiawan, Aldy Gunawan

Research Collection School Of Computing and Information Systems

This study addresses a variant of the Electric Vehicle Routing Problem with Mixed Fleet, named as the Green Mixed Fleet Vehicle Routing Problem with Realistic Energy Consumption and Partial Recharges. This problem contains three important characteristics — realistic energy consumption, partial recharging policy, and carbon emissions. An adaptive Large Neighborhood Search heuristic is developed for the problem. Experimental results show that the proposed ALNS finds optimal solutions for most small-scale benchmark instances in a significantly faster computational time compared to the performance of CPLEX solver. Moreover, it obtains high quality solutions for all medium- and large-scale instances under a reasonable …

The Multi-Vehicle Cycle Inventory Routing Problem: Formulation And A Metaheuristic Approach, Vincent F. Yu, Audrey Tedja Widjaja, Aldy Gunawan, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

This paper presents a new variant of the Multi-Vehicle Cyclic Inventory Routing Problem (MV-CIRP) which aims to determine a subset of customers to be visited, the appropriate number of vehicles used, and the corresponding cycle time and route sequence, such that the total cost (e.g. transportation, inventory, and rewards) is minimized. The MV-CIRP is formulated as a mixed-integer nonlinear programming model. We propose a Simulated Annealing (SA) based algorithm to solve the problem. SA is first tested on the available benchmark Single-Vehicle CIRP (SV-CIRP) instances and compared to the state-of-the-art algorithms. SA is then tested on the benchmark MV-CIRP instances …

An Efficient Transformer-Based Model For Vietnamese Punctuation Prediction, Hieu Tran, Cuong V. Dinh, Hong Quang Pham, Binh T. Nguyen

Research Collection School Of Computing and Information Systems

In both formal and informal texts, missing punctuation marks make the texts confusing and challenging to read. This paper aims to conduct exhaustive experiments to investigate the benefits of the pre-trained Transformer-based models on two Vietnamese punctuation datasets. The experimental results show our models can achieve encouraging results, and adding Bi-LSTM or/and CRF layers on top of the proposed models can also boost model performance. Finally, our best model can significantly bypass state-of-the-art approaches on both the novel and news datasets for the Vietnamese language. It can gain the corresponding performance up to 21.45%21.45% and 18.27%18.27% in the overall F1-scores.

Task Similarity Aware Meta Learning: Theory-Inspired Improvement On Maml, Pan Zhou, Yingtian Zpu, Xiaotong Yuan, Jiashi Feng, Caiming Xiong, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Few-shot learning ability is heavily desired for machine intelligence. By meta-learning a model initialization from training tasks with fast adaptation ability to new tasks, model-agnostic meta-learning (MAML) has achieved remarkable success in a number of few-shot learning applications. However, theoretical understandings on the learning ability of MAML remain absent yet, hindering developing new and more advanced meta learning methods in a principled way. In this work, we solve this problem by theoretically justifying the fast adaptation capability of MAML when applied to new tasks. Specifically, we prove that the learnt meta-initialization can benefit the fast adaptation to new tasks with …

Rotating Scatter Mask For Directional Radiation Detection And Imaging, Darren Holland, Robert Olesen, Larry Burggraf, Buckley O'Day, James E. Bevins

AFIT Patents

A radiation imaging system images a distributed source of radiation from an unknown direction by rotating a scatter mask around a central axis. The scatter mask has a pixelated outer surface of tangentially oriented, flat geometric surfaces that are spherically varying in radial dimension that corresponds to a discrete amount of attenuation. Rotation position of the scatter mask is tracked as a function of time. Radiation counts from gamma and/or neutron radiation are received from at least one radiation detector that is positioned at or near the central axis. A rotation-angle dependent detector response curve (DRC) is generated based on …

Counting And Sampling Small Structures In Graph And Hypergraph Data Streams, Themistoklis Haris

Dartmouth College Undergraduate Theses

In this thesis, we explore the problem of approximating the number of elementary substructures called simplices in large k-uniform hypergraphs. The hypergraphs are assumed to be too large to be stored in memory, so we adopt a data stream model, where the hypergraph is defined by a sequence of hyperedges.

First we propose an algorithm that (ε, δ)-estimates the number of simplices using O(m^1+1/k / T) bits of space. In addition, we prove that no constant-pass streaming algorithm can (ε, δ)- approximate the number of simplices using less than O( m ^1+1/k / T ) bits of space. Thus …

Object Manipulation With Modular Planar Tensegrity Robots, Maxine Perroni-Scharf

Dartmouth College Undergraduate Theses

This thesis explores the creation of a novel two-dimensional tensegrity-based mod- ular system. When individual planar modules are linked together, they form a larger tensegrity robot that can be used to achieve non-prehensile manipulation. The first half of this dissertation focuses on the study of preexisting types of tensegrity mod- ules and proposes different possible structures and arrangements of modules. The second half describes the construction and actuation of a modular 2D robot com- posed of planar three-bar tensegrity structures. We conclude that tensegrity modules are suitably adapted to object manipulation and propose a future extension of the modular 2D …

The “Knapsack Problem” Workbook: An Exploration Of Topics In Computer Science, Steven Cosares

Open Educational Resources

This workbook provides discussions, programming assignments, projects, and class exercises revolving around the “Knapsack Problem” (KP), which is widely a recognized model that is taught within a typical Computer Science curriculum. Throughout these discussions, we use KP to introduce or review topics found in courses covering topics in Discrete Mathematics, Mathematical Programming, Data Structures, Algorithms, Computational Complexity, etc. Because of the broad range of subjects discussed, this workbook and the accompanying spreadsheet files might be used as part of some CS capstone experience. Otherwise, we recommend that individual sections be used, as needed, for exercises relevant to a course in …

First Train Timetabling And Bus Service Bridging In Intermodal Bus-And-Train Transit Networks, Liujiang Kang, Hao Li, Huijun Sun, Jianjun Wu, Zhiguang Cao, Nsabimana Buhigiro

Research Collection School Of Computing and Information Systems

Subway system is the main mode of transportation for city dwellers and is a quite signif-icant backbone to a city's operations. One of the challenges of subway network operation is the scheduling of the first trains each morning and its impact on transfers. To deal with this challenge, some cities (e.g. Beijing) use bus 'bridging' services, temporarily substitut -ing segments of the subway network. The present paper optimally identifies when to start each train and bus bridging service in an intermodal transit network. Starting from a mixed integer nonlinear programming model for the first train timetabling problem, we linearize and …

Set Team Orienteering Problem With Time Windows, Aldy Gunawan, Vincent F. Yu, Andros Nicas Sutanto, Panca Jodiawan

Research Collection School Of Computing and Information Systems

This research introduces an extension of the Orienteering Problem (OP), known as Set Team Orienteering Problem with Time Windows (STOPTW), in which customers are first grouped into clusters. Each cluster is associated with a profit that will be collected if at least one customer within the cluster is visited. The objective is to find the best route that maximizes the total collected profit without violating time windows and time budget constraints. We propose an adaptive large neighborhood search algorithm to solve newly introduced benchmark instances. The preliminary results show the capability of the proposed algorithm to obtain good solutions within …

Self-Adaptive Graph Traversal On Gpus, Mo Sha, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

GPU’s massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant preprocessing costs as well as weak programmability to build general graph applications. In this paper, we introduce SAGE, a self-adaptive graph traversal on GPUs, which is free from preprocessing and operates on ubiquitous graph representations directly. We propose Tiled Partitioning and Resident Tile Stealing to fully exploit the computing power of GPUs in a runtime and self-adaptive manner. We also propose Sampling-based Reordering to further …

A Hybrid Stochastic-Deterministic Minibatch Proximal Gradient Method For Efficient Optimization And Generalization, Pan Zhou, Xiao-Tong Yuan, Lin Zhouchen, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Despite the success of stochastic variance-reduced gradient (SVRG) algorithms in solving large-scale problems, their stochastic gradient complexity often scales linearly with data size and is expensive for huge data. Accordingly, we propose a hybrid stochastic-deterministic minibatch proximal gradient (HSDMPG) algorithm for strongly convex problems with linear prediction structure, e.g. least squares and logistic/softmax regression. HSDMPG enjoys improved computational complexity that is data-size-independent for large-scale problems. It iteratively samples an evolving minibatch of individual losses to estimate the original problem, and can efficiently minimize the sampled subproblems. For strongly convex loss of n components, HSDMPG attains an -optimization-error within O κ …

Solving Chromatic Number With Quantum Search And Quantum Counting, David Lutze

Master's Theses

This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2^n/2n²(log2n)²). This is an improvement over the best known algorithm, with a run time of 2ⁿn^O(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can …

Modeling And Solving The Outsourcing Risk Management Problem In Multi-Echelon Supply Chains, Arian A. Nahangi

Master's Theses

Worldwide globalization has made supply chains more vulnerable to risk factors, increasing the associated costs of outsourcing goods. Outsourcing is highly beneficial for any company that values building upon its core competencies, but the emergence of the COVID-19 pandemic and other crises have exposed significant vulnerabilities within supply chains. These disruptions forced a shift in the production of goods from outsourcing to domestic methods.

This paper considers a multi-echelon supply chain model with global and domestic raw material suppliers, manufacturing plants, warehouses, and markets. All levels within the supply chain network are evaluated from a holistic perspective, calculating a total …

Fake News Analysis And Graph Classification On A Covid-19 Twitter Dataset, Kriti Gupta

Master's Projects

Earlier researches have showed that the spread of fake news through social media can have a huge impact to society and also to individuals in an extremely negative way. In this work we aim to study the spread of fake news compared to real news in a social network. We do that by performing classical social network analysis to discover various characteristics, and formulate the problem as a binary classification, where we have graphs modeling the spread of fake and real news. For our experiments we rely on how news are propagated through a popular social media services such as …

Improving Additional Adversarial Robustness For Classification, Michael Guo

McKelvey School of Engineering Graduate Student Theses & Dissertations

Although neural networks have achieved remarkable success on classification, adversarial robustness is still a significant concern. There are now a series of approaches for designing adversarial examples and methods to defending against them. This paper consists of two projects. In our first work, we propose an approach by leveraging cognitive salience to enhance additional robustness on top of these methods. Specifically, for image classification, we split an image into the foreground (salient region) and background (the rest) and allow significantly larger adversarial perturbations in the background to produce stronger attacks. Furthermore, we show that adversarial training with dual-perturbation attacks yield …

Reinforcement Learning For Realistic Robotic Training: A Survey, Andres Jaramillo

Honors Scholar Theses

Reinforcement learning is a widely popular topic that has resulted in a plethora of

research papers and interest from academia and industry. When applied with robotics,

the field has showed some promising signs that robots can achieve levels of complex

cognitive abilities rivaling humans, but the goal of creating sapient robots is far from

a reality due to many challenges involved with training robots in a real world setting.

This paper will provide a survey regarding the keys towards realistic robotic training by

detailing the challenges and overviewing the reinforcement learning solutions involved

in getting a robot to think like …

Semi-Supervised Spatial-Temporal Feature Learning On Anomaly-Based Network Intrusion Detection, Huy Mai

Computer Science and Computer Engineering Undergraduate Honors Theses

Due to a rapid increase in network traffic, it is growing more imperative to have systems that detect attacks that are both known and unknown to networks. Anomaly-based detection methods utilize deep learning techniques, including semi-supervised learning, in order to effectively detect these attacks. Semi-supervision is advantageous as it doesn't fully depend on the labelling of network traffic data points, which may be a daunting task especially considering the amount of traffic data collected. Even though deep learning models such as the convolutional neural network have been integrated into a number of proposed network intrusion detection systems in recent years, …

Data-Driven Approaches To Complex Materials: Applications To Amorphous Solids, Dil Kumar Limbu

Dissertations

While conventional approaches to materials modeling made significant contributions and advanced our understanding of materials properties in the past decades, these approaches often cannot be applied to disordered materials (e.g., glasses) for which accurate total-energy functionals or forces are either not available or it is infeasible to employ due to computational complexities associated with modeling disordered solids in the absence of translational symmetry. In this dissertation, a number of information-driven probabilistic methods were developed for the structural determination of a range of materials including disordered solids to transition metal clusters. The ground-state structures of transition-metal clusters of iron, nickel, and …