Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences Commons™

Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms

Institution
Keyword
Publication Year
Publication
Publication Type
File Type

Articles 1321 - 1350 of 2153

Full-Text Articles in Computer Sciences

Stochastic Multiple Gradient Decent For Inferring Action-Based Network Generators, Qian Wu, Viplove Arora, Mario Ventresca Aug 2016

Stochastic Multiple Gradient Decent For Inferring Action-Based Network Generators, Qian Wu, Viplove Arora, Mario Ventresca

The Summer Undergraduate Research Fellowship (SURF) Symposium

Networked systems, like the internet, social networks etc., have in recent years attracted the attention of researchers, specifically to develop models that can help us understand or predict the behavior of these systems. A way of achieving this is through network generators, which are algorithms that can synthesize networks with statistically similar properties to a given target network. Action-based Network Generators (ABNG)is one of these algorithms that defines actions as strategies for nodes to form connections with other nodes, hence generating networks. ABNG is parametrized using an action matrix that assigns an empirical probability distribution to vertices for choosing specific …

Go to article

A Novel Digital Image Classification Algorithm Via Low-Rank Sparse Bag-Of-Features Model, Xiu-Ming Zou, Huai-Jiang Sun, Sai Yang, Yan Zhu Aug 2016

A Novel Digital Image Classification Algorithm Via Low-Rank Sparse Bag-Of-Features Model, Xiu-Ming Zou, Huai-Jiang Sun, Sai Yang, Yan Zhu

Research Collection School of Computing and Information Systems

Bag-of-features (BoF) is one of the most well-known methods used to represent digital image features because of its simplicity and efficiency. A variety of improved algorithms have been employed to enhance the performance of BoF in characterization. However, challenges in the application of BoF in the field still exist. This study focused on BoF by decomposing local features and presented a novel framework for BoF on the basis of low-rank and sparse matrix decomposition to obtain a more robust and discriminative digital image classification. First, the local feature matrix of a digital image is decomposed into a low-rank matrix and …

Go to article

Ε-Kernel Coresets For Stochastic Points, Haitao Wang, Lingxiao Huang, Jian Li, Jeff Mark Phillips Aug 2016

Ε-Kernel Coresets For Stochastic Points, Haitao Wang, Lingxiao Huang, Jian Li, Jeff Mark Phillips

Computer Science Faculty and Staff Publications

With the dramatic growth in the number of application domains that generate probabilistic, noisy and uncertain data, there has been an increasing interest in designing algorithms for geometric or combinatorial optimization problems over such data. In this paper, we initiate the study of constructing epsilon-kernel coresets for uncertain points. We consider uncertainty in the existential model where each point's location is fixed but only occurs with a certain probability, and the locational model where each point has a probability distribution describing its location. An epsilon-kernel coreset approximates the width of a point set in any direction. We consider approximating the …

Go to article

Incremental Phylogenetics By Repeated Insertions: An Evolutionary Tree Algorithm, Peter Revesz, Zhiqiang Li Aug 2016

Incremental Phylogenetics By Repeated Insertions: An Evolutionary Tree Algorithm, Peter Revesz, Zhiqiang Li

School of Computing: Faculty Publications

We introduce the idea of constructing hypothetical evolutionary trees using an incremental algorithm that inserts species one-by-one into the current evolutionary tree. The method of incremental phylogenetics by repeated insertions lead to an algorithm that can be used on DNA, RNA and amino acid sequences. According to experimental results on both synthetic and biological data, the new algorithm generates more accurate evolutionary trees than the UPGMA and the Neighbor Joining algorithms.

Go to article

User Identity Linkage By Latent User Space Modelling, Xin Mu, Feida Zhu, Ee-Peng Lim, Jing Xiao, Jianzong Wang, Zhi-Hua Zhou Aug 2016

User Identity Linkage By Latent User Space Modelling, Xin Mu, Feida Zhu, Ee-Peng Lim, Jing Xiao, Jianzong Wang, Zhi-Hua Zhou

Research Collection School Of Computing and Information Systems

User identity linkage across social platforms is an important problem of great research challenge and practical value. In real applications, the task often assumes an extra degree of difficulty by requiring linkage across multiple platforms. While pair-wise user linkage between two platforms, which has been the focus of most existing solutions, provides reasonably convincing linkage, the result depends by nature on the order of platform pairs in execution with no theoretical guarantee on its stability. In this paper, we explore a new concept of “Latent User Space” to more naturally model the relationship between the underlying real users and their …

Go to article

An Algorithm For The Machine Calculation Of Minimal Paths, Robert Whitinger Aug 2016

An Algorithm For The Machine Calculation Of Minimal Paths, Robert Whitinger

Electronic Theses and Dissertations

Problems involving the minimization of functionals date back to antiquity. The mathematics of the calculus of variations has provided a framework for the analytical solution of a limited class of such problems. This paper describes a numerical approximation technique for obtaining machine solutions to minimal path problems. It is shown that this technique is applicable not only to the common case of finding geodesics on parameterized surfaces in R3, but also to the general case of finding minimal functionals on hypersurfaces in Rn associated with an arbitrary metric.

Go to article

Detecting Communities Using Coordination Games: A Short Paper, Radhika Arava, Pradeep Varakantham Aug 2016

Detecting Communities Using Coordination Games: A Short Paper, Radhika Arava, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Communities typically capture homophily as people of the same community share many common features. This paper is motivated by the problem of community detection in social networks, as it can help improve our understanding of the network topology. Given the selfish nature of humans to align with like-minded people, we employ game theoretic models and algorithms to detect communities in this paper. Specifically, we employ coordination games to represent interactions between individuals in a social network. We provide a novel and scalable two phased algorithm NashOverlap to compute an accurate overlapping community structure in the given network. We evaluate our …

Go to article

Comparison Of Formulations Of Applied Tasks With Intervals, Fuzzy Sets And Probability Approaches, Boris Kovalerchuk, Vladik Kreinovich Jul 2016

Comparison Of Formulations Of Applied Tasks With Intervals, Fuzzy Sets And Probability Approaches, Boris Kovalerchuk, Vladik Kreinovich

All Faculty Scholarship for the College of the Sciences

The focus of this paper is to clarify the concepts of solutions in linear equations in interval, probabilistic and fuzzy sets setting for real word tasks. There is a fundamental difference between formal definitions of the solutions and physically meaningful concept of solution in applied tasks when equations have uncertain components. For instance, a formal definition of the solution in terms of Moore interval analysis can be completely irrelevant for solving a real world task. We show that formal definitions must follow meaningful concept of the solution in the real world. The paper proposed several formalized definitions of the concept …

Go to article

Latent Semantic Indexing In The Discovery Of Cyber-Bullying In Online Text, Jacob L. Bigelow Jul 2016

Latent Semantic Indexing In The Discovery Of Cyber-Bullying In Online Text, Jacob L. Bigelow

Computer Science Summer Fellows

The rise in the use of social media and particularly the rise of adolescent use has led to a new means of bullying. Cyber-bullying has proven consequential to youth internet users causing a need for a response. In order to effectively stop this problem we need a verified method of detecting cyber-bullying in online text; we aim to find that method. For this project we look at thirteen thousand labeled posts from Formspring and create a bank of words used in the posts. First the posts are cleaned up by taking out punctuation, normalizing emoticons, and removing high and low …

Go to article

Detection Of Cyberbullying In Sms Messaging, Bryan W. Bradley Jul 2016

Detection Of Cyberbullying In Sms Messaging, Bryan W. Bradley

Computer Science Summer Fellows

Cyberbullying is a type of bullying that uses technology such as cell phones to harass or malign another person. To detect acts of cyberbullying, we are developing an algorithm that will detect cyberbullying in SMS (text) messages. Over 80,000 text messages have been collected by software installed on cell phones carried by participants in our study. This paper describes the development of the algorithm to detect cyberbullying messages, using the cell phone data collected previously. The algorithm works by first separating the messages into conversations in an automated way. The algorithm then analyzes the conversations and scores the severity and …

Go to article

Tools And Techniques For Computational Reproducibility, Stephen Piccolo, Michael B. Frampton Jul 2016

Tools And Techniques For Computational Reproducibility, Stephen Piccolo, Michael B. Frampton

Faculty Publications

When reporting research findings, scientists document the steps they followed so that others can verify and build upon the research. When those steps have been described in sufficient detail that others can retrace the steps and obtain similar results, the research is said to be reproducible. Computers play a vital role in many research disciplines and present both opportunities and challenges for reproducibility. Computers can be programmed to execute analysis tasks, and those programs can be repeated and shared with others. The deterministic nature of most computer programs means that the same analysis tasks, applied to the same data, will …

Go to article

On Understanding Preference For Agile Methods Among Software Developers, David Brian Bishop, Amit V. Deokar, Surendra Sarnikar Jul 2016

On Understanding Preference For Agile Methods Among Software Developers, David Brian Bishop, Amit V. Deokar, Surendra Sarnikar

Research & Publications

Agile methods are gaining widespread use in industry. Although management is keen on adopting agile, not all developers exhibit preference for agile methods. The literature is sparse in regard to why developers may show preference for agile. Understanding the factors informing the preference for agile can lead to more effective formation of teams, better training approaches, and optimizing software development efforts by focusing on key desirable components of agile. This study, using a grounded theory methodology, finds a variety of categories of factors that influence software developer preference for agile methods including self-efficacy, affective response, interpersonal response, external contingencies, and …

Go to article

Gene Set Enrichment And Projection: A Computational Tool For Knowledge Discovery In Transcriptomes, Karl Douglas Stamm Jul 2016

Gene Set Enrichment And Projection: A Computational Tool For Knowledge Discovery In Transcriptomes, Karl Douglas Stamm

Dissertations (1934 -)

Explaining the mechanism behind a genetic disease involves two phases, collecting and analyzing data associated to the disease, then interpreting those data in the context of biological systems. The objective of this dissertation was to develop a method of integrating complementary datasets surrounding any single biological process, with the goal of presenting the response to a signal in terms of a set of downstream biological effects. This dissertation specifically tests the hypothesis that computational projection methods overlaid with domain expertise can direct research towards relevant systems-level signals underlying complex genetic disease. To this end, I developed a software algorithm named …

Go to article

A Learning-To-Rank Based Fault Localization Approach Using Likely Invariants, Tien-Duy B. Le, David Lo, Claire Le Goues, Lars Grunske Jul 2016

A Learning-To-Rank Based Fault Localization Approach Using Likely Invariants, Tien-Duy B. Le, David Lo, Claire Le Goues, Lars Grunske

Research Collection School Of Computing and Information Systems

Debugging is a costly process that consumes much of developer time and energy. To help reduce debugging effort, many studies have proposed various fault localization approaches. These approaches take as input a set of test cases (some failing, some passing) and produce a ranked list of program elements that are likely to be the root cause of the failures (i.e., failing test cases). In this work, we propose Savant, a new fault localization approach that employs a learning-to-rank strategy, using likely invariant diffs and suspiciousness scores as features, to rank methods based on their likelihood to be a root cause …

Go to article

Scalable Greedy Algorithms For Task/Resource Constrained Multi-Agent Stochastic Planning, Pritee Agrawal, Pradeep Varakantham, William Yeoh Jul 2016

Scalable Greedy Algorithms For Task/Resource Constrained Multi-Agent Stochastic Planning, Pritee Agrawal, Pradeep Varakantham, William Yeoh

Research Collection School Of Computing and Information Systems

Synergistic interactions between task/resource allocation and stochastic planning exist in many environments such as transportation and logistics, UAV task assignment and disaster rescue. Existing research in exploiting these synergistic interactions between the two problems have either only considered domains where tasks/resources are completely independent of each other or have focussed on approaches with limited scalability. In this paper, we address these two limitations by introducing a generic model for task/resource constrained multi-agent stochastic planning, referred to as TasC-MDPs. We provide two scalable greedy algorithms, one of which provides posterior quality guarantees. Finally, we illustrate the high scalability and solution performance …

Go to article

Real-Time Salient Object Detection With A Minimum Spanning Tree, Wei-Chih Tu, Shengfeng He, Qingxiong Yang, Shao-Yi Chien Jul 2016

Real-Time Salient Object Detection With A Minimum Spanning Tree, Wei-Chih Tu, Shengfeng He, Qingxiong Yang, Shao-Yi Chien

Research Collection School Of Computing and Information Systems

In this paper, we present a real-time salient object detection system based on the minimum spanning tree. Due to the fact that background regions are typically connected to the image boundaries, salient objects can be extracted by computing the distances to the boundaries. However, measuring the image boundary connectivity efficiently is a challenging problem. Existing methods either rely on superpixel representation to reduce the processing units or approximate the distance transform. Instead, we propose an exact and iteration free solution on a minimum spanning tree. The minimum spanning tree representation of an image inherently reveals the object geometry information in …

Go to article

Optimizing The Mix Of Games And Their Locations On The Casino Floor, Jason D. Fiege, Anastasia D. Baran Jun 2016

Optimizing The Mix Of Games And Their Locations On The Casino Floor, Jason D. Fiege, Anastasia D. Baran

International Conference on Gambling & Risk Taking

We present a mathematical framework and computational approach that aims to optimize the mix and locations of slot machine types and denominations, plus other games to maximize the overall performance of the gaming floor. This problem belongs to a larger class of spatial resource optimization problems, concerned with optimizing the allocation and spatial distribution of finite resources, subject to various constraints. We introduce a powerful multi-objective evolutionary optimization and data-modelling platform, developed by the presenter since 2002, and show how this software can be used for casino floor optimization. We begin by extending a linear formulation of the casino floor …

Go to article

Stationary And Time-Dependent Optimization Of The Casino Floor Slot Machine Mix, Anastasia D. Baran, Jason D. Fiege Jun 2016

Stationary And Time-Dependent Optimization Of The Casino Floor Slot Machine Mix, Anastasia D. Baran, Jason D. Fiege

International Conference on Gambling & Risk Taking

Modeling and optimizing the performance of a mix of slot machines on a gaming floor can be addressed at various levels of coarseness, and may or may not consider time-dependent trends. For example, a model might consider only time-averaged, aggregate data for all machines of a given type; time-dependent aggregate data; time-averaged data for individual machines; or fully time dependent data for individual machines. Fine-grained, time-dependent data for individual machines offers the most potential for detailed analysis and improvements to the casino floor performance, but also suffers the greatest amount of statistical noise. We present a theoretical analysis of single …

Go to article

Application Of Computer Modeling And Simulation Techniques For Optimization Of Factory Floor Operations In Small To Medium- Sized Businesses, Brian P. Romano Jun 2016

Application Of Computer Modeling And Simulation Techniques For Optimization Of Factory Floor Operations In Small To Medium- Sized Businesses, Brian P. Romano

Theses and Dissertations

The rationale and motive for this thesis was to prove that no matter the size of a company and its particular value stream, the application of applied computer science principles with a reliance on computer modeling and simulation onto the factory floor process improves efficiencies and throughput through the reduction of downtime and/or process waiting. This thesis research specifically emphasized small businesses of between $2 and $20 million and was purposely limited to factory floor production processes and utilized standardized applied computer science techniques including simulation and modeling, microprocessor based factory floor intelligence devices. The results of this applied technology …

Go to article

Event Detection With Zero Example: Select The Right And Suppress The Wrong Concepts, Yi-Jie Lu, Hao Zhang, Maaike De Boer, Chong-Wah Ngo Jun 2016

Event Detection With Zero Example: Select The Right And Suppress The Wrong Concepts, Yi-Jie Lu, Hao Zhang, Maaike De Boer, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

Complex video event detection without visual examples is a very challenging issue in multimedia retrieval. We present a state-of-the-art framework for event search without any need of exemplar videos and textual metadata in search corpus. To perform event search given only query words, the core of our framework is a large, pre-built bank of concept detectors which can understand the content of a video in the perspective of object, scene, action and activity concepts. Leveraging such knowledge can effectively narrow the semantic gap between textual query and the visual content of videos. Besides the large concept bank, this paper focuses …

Go to article

Designing And Comparing Multiple Portfolios Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir Jun 2016

Designing And Comparing Multiple Portfolios Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir

Research Collection School Of Computing and Information Systems

Algorithm portfolios seek to determine an effective set of algorithms that can be used within an algorithm selection framework to solve problems. A limited number of these portfolio studies focus on generating different versions of a target algorithm using different parameter configurations. In this paper, we employ a Design of Experiments (DOE) approach to determine a promising range of values for each parameter of an algorithm. These ranges are further processed to determine a portfolio of parameter configurations, which would be used within two online Algorithm Selection approaches for solving different instances of a given combinatorial optimization problem effectively. We …

Go to article

Robust Partial Order Schedules For Rcpsp/Max With Durational Uncertainty, Na Fu, Pradeep Varakantham, Hoong Chuin Lau Jun 2016

Robust Partial Order Schedules For Rcpsp/Max With Durational Uncertainty, Na Fu, Pradeep Varakantham, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this work, we consider RCPSP/max with durational uncertainty. We focus on computing robust Partial Order Schedules (or, in short POS) which can be executed with risk controlled feasibility and optimality, i.e., there is stochastic posteriori quality guarantee that the derived POS can be executed with all constraints honored and completion before robust makespan. To address this problem, we propose BACCHUS: a solution method on Benders Accelerated Cut Creation for Handling Uncertainty in Scheduling. In our proposed approach, we first give an MILP formulation for the deterministic RCPSP/max and partition the model into POS generation process and start time schedule …

Go to article

Packet Filter Approach To Detect Denial Of Service Attacks, Essa Yahya M Muharish Jun 2016

Packet Filter Approach To Detect Denial Of Service Attacks, Essa Yahya M Muharish

Electronic Theses, Projects, and Dissertations

Denial of service attacks (DoS) are a common threat to many online services. These attacks aim to overcome the availability of an online service with massive traffic from multiple sources. By spoofing legitimate users, an attacker floods a target system with a high quantity of packets or connections to crash its network resources, bandwidth, equipment, or servers. Packet filtering methods are the most known way to prevent these attacks via identifying and blocking the spoofed attack from reaching its target. In this project, the extent of the DoS attacks problem and attempts to prevent it are explored. The attacks categories …

Go to article

The Contributions Of Anatol Rapoport To Game Theory, Erika Simpson May 2016

The Contributions Of Anatol Rapoport To Game Theory, Erika Simpson

Political Science Publications

Game theory is used to rationally and dispassionately examine the strategic behaviour of nations, especially superpower behaviour. This article explains how basic game theory - at its simplest level - was used by Anatol Rapoport to generate ideas about how to enhance world peace. Rapoport was at the forefront of the game theoreticians who sought to conceptualize strategies that could promote international cooperation. Accordingly, the basic logic of game theory is explained using the game models of ‘Chicken’ and ‘Prisoner’s Dilemma’. These models were used by Rapoport in his books and lectures in simple and complex ways. Then Rapoport’s revolutionary …

Go to article

Ant Colony Optimization For Continuous Spaces, Rachel Findley May 2016

Ant Colony Optimization For Continuous Spaces, Rachel Findley

Computer Science and Computer Engineering Undergraduate Honors Theses

Ant Colony Optimization (ACO) is an optimization algorithm designed to find semi-optimal solutions to Combinatorial Optimization Problems. The challenge of modifying this algorithm to effectively optimize over a continuous domain is one that has been tackled by several researchers. In this paper, ACO has been modified to use several variations of the algorithm for continuous spaces. An aspect of ACO which is crucial to its success when optimizing over a continuous space is choosing the appropriate object (solution component) out of an infinite set to add to the ant's path. This step is highly important in shaping good solutions. Important …

Go to article

An Arithmetic-Based Deterministic Centroid Initialization Method For The K-Means Clustering Algorithm, Matthew Michael Mayo May 2016

An Arithmetic-Based Deterministic Centroid Initialization Method For The K-Means Clustering Algorithm, Matthew Michael Mayo

Theses and Dissertations

One of the greatest challenges in k-means clustering is positioning the initial cluster centers, or centroids, as close to optimal as possible, and doing so in an amount of time deemed reasonable. Traditional fc-means utilizes a randomization process for initializing these centroids, and poor initialization can lead to increased numbers of required clustering iterations to reach convergence, and a greater overall runtime. This research proposes a simple, arithmetic-based deterministic centroid initialization method which is much faster than randomized initialization. Preliminary experiments suggest that this collection of methods, referred to herein as the sharding centroid initialization algorithm family, often outperforms random …

Go to article

An Exploration Of Rule Clustering In Cellular Automata Rule Spaces, Jordon Huffman May 2016

An Exploration Of Rule Clustering In Cellular Automata Rule Spaces, Jordon Huffman

Theses and Dissertations

The study of complex systems examines the global behavior of a system and how the individual parts of the system affect that behavior [1]. The study of complex systems spans across many fields of science like biology, physics, engineering, and computer science. One area of complex systems that has not been fully explored is cellular automata. Since its discovery by John von Neumann, there have been no consistent ways of categorizing similarities between cellular automata rules or collecting similar rules for observation. This thesis introduces an approach to identifying clusters of similar rules and extracting rules from that cluster. Several …

Go to article

Sparse Feature Learning For Image Analysis In Segmentation, Classification, And Disease Diagnosis., Ehsan Hosseini-Asl May 2016

Sparse Feature Learning For Image Analysis In Segmentation, Classification, And Disease Diagnosis., Ehsan Hosseini-Asl

Electronic Theses and Dissertations

The success of machine learning algorithms generally depends on intermediate data representation, called features that disentangle the hidden factors of variation in data. Moreover, machine learning models are required to be generalized, in order to reduce the specificity or bias toward the training dataset. Unsupervised feature learning is useful in taking advantage of large amount of unlabeled data, which is available to capture these variations. However, learned features are required to capture variational patterns in data space. In this dissertation, unsupervised feature learning with sparsity is investigated for sparse and local feature extraction with application to lung segmentation, interpretable deep …

Go to article

Deeper Look Into Bug Fixes: Patterns, Replacements, Deletions, And Additions, Mauricio Soto, Ferdian Thung, Chu-Pan Wong, Claire Le Goues, David Lo May 2016

Deeper Look Into Bug Fixes: Patterns, Replacements, Deletions, And Additions, Mauricio Soto, Ferdian Thung, Chu-Pan Wong, Claire Le Goues, David Lo

Research Collection School Of Computing and Information Systems

Many implementations of research techniques that automatically repair software bugs target programs written in C. Work that targets Java often begins from or compares to direct translations of such techniques to a Java context. However, Java and C are very different languages, and Java should be studied to inform the construction of repair approaches to target it. We conduct a large-scale study of bugfixing commits in Java projects, focusing on assumptions underlying common search-based repair approaches. We make observations that can be leveraged to guide high quality automatic software repair to target Java specifically, including common and uncommon statement modifications …

Go to article

A Horizon Decomposition Approach For The Capacitated Lot-Sizing Problem With Setup Times, Ioannis Fragkos, Zeger Degraeve, Bert De Reyck May 2016

A Horizon Decomposition Approach For The Capacitated Lot-Sizing Problem With Setup Times, Ioannis Fragkos, Zeger Degraeve, Bert De Reyck

Research Collection Lee Kong Chian School Of Business

We introduce horizon decomposition in the context of Dantzig-Wolfe decomposition, and apply it to the capacitated lot-sizing problem with setup times. We partition the problem horizon in contiguous overlapping intervals and create subproblems identical to the original problem, but of smaller size. The user has the flexibility to regulate the size of the master problem and the subproblem via two scalar parameters. We investigate empirically which parameter configurations are efficient, and assess their robustness at different problem classes. Our branch-and-price algorithm outperforms state-of-the-art branch-and-cut solvers when tested to a new data set of challenging instances that we generated. Our methodology …

Go to article

First Prev Next Last