Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Engineering (730)
- Computer Engineering (697)
- Artificial Intelligence and Robotics (25)
- Electrical and Computer Engineering (13)
- Electrical and Electronics (10)
-
- Theory and Algorithms (9)
- Life Sciences (8)
- Biomedical Engineering and Bioengineering (7)
- Graphics and Human Computer Interfaces (7)
- Data Science (5)
- Medicine and Health Sciences (5)
- Social and Behavioral Sciences (5)
- Statistics and Probability (5)
- Information Security (4)
- Numerical Analysis and Scientific Computing (4)
- Other Computer Sciences (4)
- Bioinformatics (3)
- Computer and Systems Architecture (3)
- Education (3)
- Analytical, Diagnostic and Therapeutic Techniques and Equipment (2)
- Applied Mathematics (2)
- Astrophysics and Astronomy (2)
- Biology (2)
- Computational Engineering (2)
- Control Theory (2)
- Controls and Control Theory (2)
- Curriculum and Instruction (2)
- Databases and Information Systems (2)
- Keyword
-
- Machine Learning (11)
- Machine learning (10)
- Optimization (6)
- Deep Learning (5)
- Computer vision (4)
-
- Deep learning (4)
- AI (3)
- Trust (3)
- Virtualization (3)
- Active learning (2)
- Algorithms (2)
- Bayesian (2)
- Bayesian optimization (2)
- Benchmark (2)
- Biomedical informatics;Deep learning;disease progression;Multimodal representation learning (2)
- ChatGPT (2)
- Computer Vision (2)
- Computer graphics (2)
- Computer vision;cyber physical systems;efficiency;machine learning;machine vision;trustworthy (2)
- Cyber-physical systems (2)
- Data Visualization (2)
- Distributed Embedded Systems (2)
- Electronic health record (2)
- Gated recurrent unit (2)
- Healthcare;Internet of Medical Things;Machine Learning;Wearable (2)
- Heuristic Search (2)
- Individual work (2)
- LLM (2)
- Large language models (2)
- Logic simulation (2)
- Publication Year
- Publication
- Publication Type
Articles 331 - 360 of 830
Full-Text Articles in Computer Sciences
A Fingerspelling Sign Language Visualization , Carol S. Brickman
A Fingerspelling Sign Language Visualization , Carol S. Brickman
All Computer Science and Engineering Research
The goal of the Fingerspell Visualization Project is to research methods to improve learning of reading skills through sign language. The techniques are centered on Fingerspelling as the method to bridge stages of skill development. Visualization of a string of text in images of a hand performing the letters of the alphabet in standardized fingerspell sign language positions provide Full Motion Learning as opposed to learning from single pictures.
Determining Alpha-Helix Correspondence For Protein Structure Prediction From Cryo-Em Density Maps, Master's Thesis, May 2007, Sasakthi S. Abeysinghe
Determining Alpha-Helix Correspondence For Protein Structure Prediction From Cryo-Em Density Maps, Master's Thesis, May 2007, Sasakthi S. Abeysinghe
All Computer Science and Engineering Research
Determining protein structure is an important problem for structural biologists, which has received a significant amount of attention in the recent years. In this thesis, we describe a novel, shape-modeling approach as an intermediate step towards recovering 3D protein structures from volumetric images. The input to our method is a sequence of alpha-helices that make up a protein, and a low-resolution volumetric image of the protein where possible locations of alpha-helices have been detected. Our task is to identify the correspondence between the two sets of helices, which will shed light on how the protein folds in space. The central …
Dna Repair In Incipient Alzheimer's Disease, Monika Ray, Weixiong Zhang
Dna Repair In Incipient Alzheimer's Disease, Monika Ray, Weixiong Zhang
All Computer Science and Engineering Research
Alzheimer’s disease (AD) is a progressive neurodegenerative disorder currently with no cure. Understanding the pathogenesis in the early stages of late-onset AD can help gain important mechanistic insights into this disease as well as aid in effective drug development. The analysis of incipient AD is steeped in difficulties due to its slight pathological and genetic differences from normal ageing. The difficulty also lies in the choice of analysis techniques as statistical power to analyse incipient AD with a small sample size, as is common in pilot studies, can be low if the proper analytical tool is not employed. In this …
Mlds: A Flexible Location Directory Service For Tiered Sensor Networks, Sangeeta Bhattacharya, Chien-Liang Fok, Chenyang Lu, Gruia-Catalin Roman
Mlds: A Flexible Location Directory Service For Tiered Sensor Networks, Sangeeta Bhattacharya, Chien-Liang Fok, Chenyang Lu, Gruia-Catalin Roman
All Computer Science and Engineering Research
Many emergent distributed sensing applications need to keep track of mobile entities across multiple sensor networks connected via an IP network. To simplify the realization of such applications, we present MLDS, a Multi-resolution Location Directory Service for tiered sensor networks. MLDS provides a rich set of spatial query services ranging from simple queries about entity location, to complex nearest neighbor queries. Furthermore, MLDS supports multiple query granularities which allow an application to achieve the desired tradeoff between query accuracy and communication cost. We implemented MLDS on Agimone, a unified middleware for sensor and IP networks. We then deployed and evaluated …
Real-Time Query Scheduling For Wireless Sensor Networks, Octav Chipara, Chenyang Lu, Gruia-Catalin Roman
Real-Time Query Scheduling For Wireless Sensor Networks, Octav Chipara, Chenyang Lu, Gruia-Catalin Roman
All Computer Science and Engineering Research
Recent years have seen the emergence of wireless sensor network (WSN) systems that require high data rate real-time communication. This paper proposes Real-Time Query Scheduling (RTQS), a novel approach to conflict-free transmission scheduling for real-time queries in WSNs. We show that there is an inherent trade-off between prioritization and throughput in conflict-free query scheduling. RTQS provides three new real-time scheduling algorithms. The non-preemptive query scheduling algorithm achieves high throughput while introducing priority inversions. The preemptive query scheduling algorithm eliminates priority inversion at the cost of reduced throughput. The slack stealing query scheduling algorithm combines the benefits of preemptive and non-preemptive …
A Duality Theory With Zero Duality Gap For Nonlinear Programming, Yixin Chen
A Duality Theory With Zero Duality Gap For Nonlinear Programming, Yixin Chen
All Computer Science and Engineering Research
Duality is an important notion for constrained optimization which provides a theoretical foundation for a number of constraint decomposition schemes such as separable programming and for deriving lower bounds in space decomposition algorithms such as branch and bound. However, the conventional duality theory has the fundamental limit that it leads to duality gaps for nonconvex optimization problems, especially discrete and mixed-integer problems where the feasible sets are nonconvex. In this paper, we propose a novel extended duality theory for nonlinear optimization that overcomes some limitations of previous dual methods. Based on a new dual function, the extended duality theory leads …
Hexa: Compact Data Structures For Faster Packet Processing, Sailesh Kumar, Jonathan Turner, Patrick Crowley, Michael Mitzenmacher
Hexa: Compact Data Structures For Faster Packet Processing, Sailesh Kumar, Jonathan Turner, Patrick Crowley, Michael Mitzenmacher
All Computer Science and Engineering Research
Directed graphs with edge labels are used in packet processing algorithms for a variety of network applications. In this paper we present a novel representation for such graph that significantly reduces the memory required for such graphs. This approach called History-based Encoding, eXecution and Addressing (HEXA) challenges the conventional assumption that graph data structures must store pointers of log2n bits to identify successor nodes. HEXA takes advantage of implict information to reduce the information that must be stored explicitly. We demonstrate that the binary tries used for IP route lookup can be implemented using just two bytes per stored prefix …
Architecture For Document Clustering In Reconfigurable Hardware, Master's Thesis, December 2006, Adam G. Covington
Architecture For Document Clustering In Reconfigurable Hardware, Master's Thesis, December 2006, Adam G. Covington
All Computer Science and Engineering Research
High-performance document clustering systems enable similar documents to automatically self-organize into groups. In the past, the large amount of computational time needed to cluster documents prevented practical use of such systems with a large number of documents. A full hardware implementation of K-means clustering has been designed and implemented in reconfigurable hardware that rapidly clusters a half million documents. Documents and concepts are represented as vectors with 4000 dimensions. The circuit was implemented in Field Programmable Gate Array (FPGA) logic and uses four parallel cosine distance metrics to cluster document vectors together. An exploration of the effect of the integer …
Single Cell Expression Profiling Reveals Major Disruption Of Dna Repair Capacity In Incipient Alzheimer's Disease, Monika Ray, Weixiong Zhang
Single Cell Expression Profiling Reveals Major Disruption Of Dna Repair Capacity In Incipient Alzheimer's Disease, Monika Ray, Weixiong Zhang
All Computer Science and Engineering Research
Understanding the pathogenesis in the early stages of late-onset Alzheimer's disease (LOAD) can help in gaining important mechanistic insights into this devastating neurodegenerative disorder. Alzheimer's disease (AD) is characterised by extensive cell death with disease progression. In this paper laser capture microdissection (LCM) based gene expression profiling, which is able to profile gene expression in a single cell type, is employed to analyse the gene expression regulation of incipient AD. Our analysis shows that LCM based gene expression profiling of neurons has a critical advantage over the conventional gene expression profiling method which uses samples of mixed cell types and …
Price Of Asynchrony: Queuing Under Ideally Smooth Congestion Control, Maxim Podlesny, Sergey Gorinsky
Price Of Asynchrony: Queuing Under Ideally Smooth Congestion Control, Maxim Podlesny, Sergey Gorinsky
All Computer Science and Engineering Research
The ability of TCP (Transmission Control Protocol) or alternative congestion control algorithms to operate successfully in networks with small link buffers has recently become a subject of intensive research. In this paper, we investigate fundamental limitations on minimum buffer requirements for any congestion control. We present an idealized protocol where all flows always transmit at their fair rates. The ideally smooth congestion control causes link queuing only due to asynchrony of flow arrivals, which is intrinsic to computer networks. Our analysis and simulations for different distributions of flow interarrival times agree that the buffer size needed for a fixed loss …
Distributed Allocation Of Workflow Tasks In Manets, Rohan Sen, Gruia-Catalin Roman, Christopher Gill
Distributed Allocation Of Workflow Tasks In Manets, Rohan Sen, Gruia-Catalin Roman, Christopher Gill
All Computer Science and Engineering Research
When multiple participants work on a workflow that represents a large, collaborative activity, it is important to have a well defined process to determine the portions of the workflow that each participant is responsible for executing. In this paper, we describe a process and related algorithms required to assign tasks in a workflow, to hosts that are willing to carry out the execution of these tasks, and thereby contributing to the completion of the activity. This problem is a stylized form of the multi-processor scheduling algorithm which has been shown to be NP-Hard. Further complicating the issue is that we …
Implementing Legba: Fine-Grained Memory Protection, Sheffield, Sowell, Wilson
Implementing Legba: Fine-Grained Memory Protection, Sheffield, Sowell, Wilson
All Computer Science and Engineering Research
Fine-grained hardware protection could provide a powerful and effective means for isolating untrusted code. However, previous techniques for providing fine-grained protection in hardware have lead to poor performance. Legba has been proposed as a new caching architecture, designed to reduce the granularity of protection, without slowing down the processor. Unfortunately, the designers of Legba have not attempted an implementation. Instead, all of their analysis is based purely on simulations. We present an implementation of the Legba design on a MIPS Core Processor, along with an analysis of our observations and results.
Customizing Component Middleware For Distributed Real-Time Systems With Aperiodic And Periodic Tasks, Yuanfang Zhang, Christopher Gill, Chenyang Lu
Customizing Component Middleware For Distributed Real-Time Systems With Aperiodic And Periodic Tasks, Yuanfang Zhang, Christopher Gill, Chenyang Lu
All Computer Science and Engineering Research
Many distributed real-time applications must handle mixed aperiodic and periodic tasks with diverse requirements. However, existing middleware lacks flexible configuration mechanisms needed to manage end-to-end timing easily for a wide range of different applications with both aperiodic and periodic tasks. The primary contribution of this work is the design, implementation and performance evaluation of the first configurable component middleware services for admission control and load balancing of aperiodic and periodic tasks in distributed real-time systems. Empirical results demonstrate the need for, and the effectiveness of, our configurable component middleware approach in supporting different applications with aperiodic and periodic tasks.
Configuring Low Cost Metanetworks On A Shared Substrate, Jing Lu, Jonathan Turner
Configuring Low Cost Metanetworks On A Shared Substrate, Jing Lu, Jonathan Turner
All Computer Science and Engineering Research
In a diversified internet, meta-networks (“metanets?for short) share a common substrate and offer value-added services to millions of users around the globe. Therefore, configuring low-cost metanets with links having enough bandwidth to accommodate all anticipated user traffic is critical to the success of the metanets. In this paper, we propose a novel pruning algorithm that configures metanets on any given substrate in a cost-efficient way. In contrast to other testbed configuration systems, we solve the metanet configuration problem from a higher level specification and produces a network that is dimensioned to handle the specified traffic. To the best of our …
Combined Controllers That Follow Imperfect Input Motions For Humanoid Robots, Gazihan Alankus, Burchan O. Bayazit
Combined Controllers That Follow Imperfect Input Motions For Humanoid Robots, Gazihan Alankus, Burchan O. Bayazit
All Computer Science and Engineering Research
Humanoid robots have the potential to become a part of everyday life as their hardware and software challenges are being solved. In this paper we present a system that gets as input a motion trajectory in the form of motion capture data, and produces a controller that controls a humanoid robot in real-time to achieve a motion trajectory that is similar to the input motion data. The controller expects the input motion data not to be dynamically feasible for the robot and employs a combined controller with corrective components to keep the robot balanced while following the motion. Since the …
Link Layer Support For Unified Radio Power Management In Wireless Sensor Networks, Master's Thesis, May 2007, Kevin Klues
Link Layer Support For Unified Radio Power Management In Wireless Sensor Networks, Master's Thesis, May 2007, Kevin Klues
All Computer Science and Engineering Research
Radio power management is of paramount concern in wireless sensor networks that must achieve long lifetimes on scarce amounts of energy. While a multitude of power management protocols have been proposed in the past, the lack of system support for flexibly integrating them with a diverse set of applications and network platforms has made them difficult to use. Instead of proposing yet another power management protocol, this thesis focuses on providing link layer support towards realizing a Unified Power Management Architecture (UPMA) for flexible radio power management in wireless sensor networks. In contrast to the monolithic approaches adopted by existing …
Mobile Wireless Sensor Network Connectivity Repair With K-Redundanc, Nuzhet Atay, Burchan Bayazit
Mobile Wireless Sensor Network Connectivity Repair With K-Redundanc, Nuzhet Atay, Burchan Bayazit
All Computer Science and Engineering Research
Connectivity is an important requirement for wireless sensor networks especially in real-time monitoring and data transfer applications. However, node movements and failures change the topology of the initial deployed network, which can result in partitioning of the communication graph. In this paper, we present a method for maintaining and repairing the communication network of a dynamic mobile wireless sensor network. We assume that we cannot control the motion of wireless sensor nodes, but there are robots whose motion can be controlled by the wireless sensor nodes to maintain and repair the connectivity of the network. At the heart of our …
Curing Regular Expressions Matching Algorithms From Insomnia, Amnesia, And Acalulia, Sailesh Kumar, Balakrishnan Chandrasekaran, Jonathan Turner, George Varghese
Curing Regular Expressions Matching Algorithms From Insomnia, Amnesia, And Acalulia, Sailesh Kumar, Balakrishnan Chandrasekaran, Jonathan Turner, George Varghese
All Computer Science and Engineering Research
The importance of network security has grown tremendously and a collection of devices have been introduced, which can improve the security of a network. Network intrusion detection systems (NIDS) are among the most widely deployed such system; popular NIDS use a collection of signatures of known security threats and viruses, which are used to scan each packet's payload. Today, signatures are often specified as regular expressions; thus the core of the NIDS comprises of a regular expressions parser, such parsers are traditionally implemented as finite automata. Deterministic Finite Automata (DFA) are fast, therefore they are often desirable at high network …
Optimal Discrete Rate Adaptation For Distributed Real-Time Systems, Yingming Chen, Chenyang Lu, Xenofon Kutsoukos
Optimal Discrete Rate Adaptation For Distributed Real-Time Systems, Yingming Chen, Chenyang Lu, Xenofon Kutsoukos
All Computer Science and Engineering Research
Many distributed real-time systems face the challenge of dynamically maximizing system utility in response to fluctuations in system workload. We present the MultiParametric Rate Adaptation (MPRA) algorithm for discrete rate adaptation in distributed real-time systems with end-to-end tasks. The key novelty and advantage of MPRA is that it can efficiently produce optimal solutions in response to workload variations such as dynamic task arrivals. Through offline preprocessing MPRA transforms an NP-hard utility optimization problem to the evaluation of a piecewise linear function of the CPU utilization. At run time MPRA produces optimal solutions by evaluating the function based on the CPU …
Context-Aware Publish Subscribe In Mobile Ad Hoc Networks, Davide Frey, Gruia-Catalin Roman
Context-Aware Publish Subscribe In Mobile Ad Hoc Networks, Davide Frey, Gruia-Catalin Roman
All Computer Science and Engineering Research
The publish-subscribe communication paradigm is enjoying increasing popularity thanks to its ability to simplify the development of complex distributed applications. However, existing solutions in the publish-subscribe domain address only part of the challenges associated with the development of applications in dynamic scenarios such as mobile ad hoc networks. Mobile applications must be able to assist users in a variety of situations, responding not only to their inputs but also to the characteristics of the environment in which they operate. In this paper, we address these challenges by extending the publish-subscribe paradigm with the ability to manage and exploit context information …
Roadmap Analysis Of Protein-Protein Interactions. Master's Thesis, August 2007, Brian C. Haynes
Roadmap Analysis Of Protein-Protein Interactions. Master's Thesis, August 2007, Brian C. Haynes
All Computer Science and Engineering Research
The ability to effectively model the interaction between proteins is an important and open problem. In molecular biology it is well accepted that from sequence arises form and from form arises function but relating structure to function remains a challenge. The function of a given protein is defined by its interactions. Likewise a malfunction or a change in protein-protein interactions is a hallmark of many diseases. Many researchers are studying the mechanisms of protein-protein interactions and one of the overarching goals of the community is to predict whether two proteins will bind, and if so what the final conformation will …
Gigabit Concept Mining: A Sensitivity Analysis, Masters Thesis, December 2006, Andrew Levine
Gigabit Concept Mining: A Sensitivity Analysis, Masters Thesis, December 2006, Andrew Levine
All Computer Science and Engineering Research
Massive amounts of data are passed over public networks. There is a need for network administrators to analyze this traffic, but it was not previously possible to analyze live network data at high speed. It has been shown that streaming computation and deep packet analysis are possible at very high rates through the use of hardware acceleration. This work provides analysis for a larger project that involves digesting large amounts of network traffic. In this system, we process the traffic using hardware that has constraints. The workings of the system are first discussed. Tradeoffs in the design of hardware and …
Leveraging Est Evidence To Automatically Predict Alternatively Spliced Genes, Master's Thesis, December 2006, Robert Zimmermann
Leveraging Est Evidence To Automatically Predict Alternatively Spliced Genes, Master's Thesis, December 2006, Robert Zimmermann
All Computer Science and Engineering Research
Current methods for high-throughput automatic annotation of newly sequenced genomes are largely limited to tools which predict only one transcript per gene locus. Evidence suggests that 20-50% of genes in higher eukariotic organisms are alternatively spliced. This leaves the remainder of the transcripts to be annotated by hand, an expensive time-consuming process. Genomes are being sequenced at a much higher rate than they can be annotated. We present three methods for using the alignments of inexpensive Expressed Sequence Tags in combination with HMM-based gene prediction with N-SCAN EST to recreate the vast majority of hand annotations in the D.melanogaster genome. …
The Effect Of Object Color On Depth Ordering, Reynold Bailey, Cindy Grimm, Christopher Davoli, Richard Abrams
The Effect Of Object Color On Depth Ordering, Reynold Bailey, Cindy Grimm, Christopher Davoli, Richard Abrams
All Computer Science and Engineering Research
The relationship between color and perceived depth for realistic, colored objects with varying shading was explored. Background: Studies have shown that warm-colored stimuli tend to appear nearer in depth than cool-colored stimuli. The majority of these studies asked human observers to view physically equidistant, colored stimuli and compare them for relative depth. However, in most cases, the stimuli presented were rather simple: straight colored lines, uniform color patches, point light sources, or symmetrical objects with uniform shading. Additionally, the colors were typically highly saturated. Although such stimuli are useful for isolating and studying depth cues in certain contexts, they leave …
Control Of A Robotic Arm Using Low-Dimensional Emg And Ecog Biofeedback, Timothy M. Blackely, William D. Smart
Control Of A Robotic Arm Using Low-Dimensional Emg And Ecog Biofeedback, Timothy M. Blackely, William D. Smart
All Computer Science and Engineering Research
In this dissertation we describe a system that uses a low dimensional input derived from electromyography and electrocorticography data to control a robot. The work involves creating a system that allows signals recorded directly from a human body to allow control of a small robot arm. We compare direct joystick control with electromyogram (EMG) input to determine if one input system is superior, or if the quality of control between them is comparable. We also verify the system that is used to record the electromyogram signals is adaptable to other forms of biosignal input; in particular, direct connection to a …
Splice: A Standardized Peripheral Logic And Interface Creation Engine, Master's Thesis, May 2007, Justin Thiel
Splice: A Standardized Peripheral Logic And Interface Creation Engine, Master's Thesis, May 2007, Justin Thiel
All Computer Science and Engineering Research
Recent advancements in FPGA technology have allowed manufacturers to place general-purpose processors alongside user-configurable logic gates on a single chip. At first glance, these integrated devices would seem to be the ideal deployment platform for hardware-software co-designed systems, but some issues, such as incompatibility across vendors and confusion over which bus interfaces to support, have impeded adoption of these platforms. This thesis describes the design and operation of Splice, a software-based code generation tool intended to address these types of issues by providing a bus-independent structure that allows end-users to easily integrate their customized peripheral logic into embedded systems. To …
Experimental Evaluation Of A Coarse-Grained Switch Scheduler, Charlie Wiseman, Jon Turner, Ken Wong, Brandon Heller
Experimental Evaluation Of A Coarse-Grained Switch Scheduler, Charlie Wiseman, Jon Turner, Ken Wong, Brandon Heller
All Computer Science and Engineering Research
Modern high performance routers rely on sophisticated interconnection networks to meet ever increasing demands on capacity. Regulating the flow of packets through these interconnects is critical to providing good performance, particularly in the presence of extreme traffic patterns that result in sustained overload at output ports. Previous studies have used a combination of analysis and idealized simulations to show that coarse-grained scheduling of traffic flows can be effective in preventing congestion, while ensuring high utilization. In this paper, we study the performance of a coarse-grained scheduler in a real router with a scalable architecture similar to those found in high …
A Comprehensive Analysis Of The Effect Of Microarray Data, Monika Ray, Johannes Freudenberg, Weixiong Zhang
A Comprehensive Analysis Of The Effect Of Microarray Data, Monika Ray, Johannes Freudenberg, Weixiong Zhang
All Computer Science and Engineering Research
Background: Microarray data preprocessing, such as differentially expressed (DE) genes selection, is performed prior to higher level statistical analysis in order to account for technical variability. Preprocessing for the Affymetrix GeneChip includes background correction, normalisation and summarisation. Numerous preprocessing methods have been proposed with little consensus as to which is the most suitable. Furthermore, due to poor concordance among results from cross-platform analyses, protocols are being developed to enable cross-platform reproducibility. However, the effect of data analysis on a single platform is still unknown. The objective of our study is two-fold: first to determine whether there is consistency in the …
The Meta-Theory Of Q_0 In The Calculus Of Inductive Constructions, Master's Thesis, May 2006, Li-Yang Tan
The Meta-Theory Of Q_0 In The Calculus Of Inductive Constructions, Master's Thesis, May 2006, Li-Yang Tan
All Computer Science and Engineering Research
The notion of a proof is central to all of mathematics. In the language of formal logic, a proof is a finite sequence of inferences from a set of axioms, and any statement one yields from such a finitistic procedure is called a theorem. For better or for worse, this is far from the form a traditional mathematical proof takes. Mathematicians write proofs that omit routine logical steps, and details deemed tangential to the central result are often elided. These proofs are fuzzy and human-centric, and a great amount of context is assumed on the part of the reader. While …
The Remote-Clique Problem Revisited, Benjamin E. Birnbaum
The Remote-Clique Problem Revisited, Benjamin E. Birnbaum
All Computer Science and Engineering Research
Given a positive integer k and a complete graph with non-negative edge weights that satisfy the triangle inequality, the remote-clique problem is to find a subset of k vertices having a maximum-weight induced subgraph. A greedy algorithm for the problem has been shown to have an approximation ratio of 4, but this analysis was not shown to be tight. In this thesis, we present an algorithm called d-Greedy Augment that generalizes this greedy algorithm (they are equivalent when d = 1). We use the technique of factor-revealing linear programs to prove that d-Greedy Augment, which has a running time of …