Digital Commons Network^™

Geometric Facility Location Problems On Uncertain Data, Jingru Zhang

All Graduate Theses and Dissertations, Spring 1920 to Summer 2023

In this dissertation, we study several facility location problems on uncertain data. We mainly consider the k-center problem and many of its variations. These are classical problems in computer science and operations research. These problems on deterministic data have been studied extensively in the literature. We consider them on uncertain data because data in the real world is often associated with uncertainty due to measurement inaccuracy, sampling discrepancy, outdated data sources, resource limitation, etc. Although we focus on the theoretical study, the algorithms developed in this dissertation may find applications in other areas such as data clustering, wireless sensor …

Mechanism Design In Sequencing Problems., Parikshit De Dr.

Doctoral Theses

Collective decision making is an important social issue, since it depends on individual preferences that are not publicly observable. Therefore, the question is, whether it is possible to elicit the private information available to individuals and then how to extract the private information in various strategic environment; Mechanism design deals with these questions. The difference between game theory and mechanism design is that, the former tries to predict the outcome of a strategic environment in some “equilibrium” but the latter tries to design or restrict the environment in such a way that the desired objective is attained, that is, the …

Generalized Differential Calculus And Applications To Optimization, R. Blake Rector

Dissertations and Theses

This thesis contains contributions in three areas: the theory of generalized calculus, numerical algorithms for operations research, and applications of optimization to problems in modern electric power systems. A geometric approach is used to advance the theory and tools used for studying generalized notions of derivatives for nonsmooth functions. These advances specifically pertain to methods for calculating subdifferentials and to expanding our understanding of a certain notion of derivative of set-valued maps, called the coderivative, in infinite dimensions. A strong understanding of the subdifferential is essential for numerical optimization algorithms, which are developed and applied to nonsmooth problems in operations …

Crowd Data Analytics And Optimization, Habibur Rahman

Computer Science and Engineering Dissertations

Crowdsourcing can be defined as outsourcing with crowd, where crowd refers to the online workers who are willing to complete simple tasks for small monetary compensation. The overwhelming reach of internet has enabled us to exploit crowd in an unprecedented way. Crowdsourcing, nowadays, is considered as a tool to solve both simple tasks (such as labeling ground truth, image recognition etc.) and complex tasks (such as collaborative writing, citizen journalism etc.). Furthermore, it is also used to solve computational problems such as Entity Resolution, Top-k, Group-by etc. While crowdsourcing provides us with plenty of opportunities, it also presents us with …

Inference In Networking Systems With Designed Measurements, Chang Liu

Doctoral Dissertations

Networking systems consist of network infrastructures and the end-hosts have been essential in supporting our daily communication, delivering huge amount of content and large number of services, and providing large scale distributed computing. To monitor and optimize the performance of such networking systems, or to provide flexible functionalities for the applications running on top of them, it is important to know the internal metrics of the networking systems such as link loss rates or path delays. The internal metrics are often not directly available due to the scale and complexity of the networking systems. This motivates the techniques of inference …

Certifying Loop Pipelining Transformations In Behavioral Synthesis, Disha Puri

Dissertations and Theses

Due to the rapidly increasing complexity in hardware designs and competitive time to market trends in the industry, there is an inherent need to move designs to a higher level of abstraction. Behavioral Synthesis is the process of automatically compiling such Electronic System Level (ESL) designs written in high-level languages such as C, C++ or SystemC into Register-Transfer Level (RTL) implementation in hardware description languages such as Verilog or VHDL. However, the adoption of this flow is dependent on designers' faith in the correctness of behavioral synthesis tools.

Loop pipelining is a critical transformation employed in behavioral synthesis process, and …

Computational Algorithms For Improved Representation Of The Model Error Covariance In Weak-Constraint 4d-Var, Jeremy A. Shaw

Dissertations and Theses

Four-dimensional variational data assimilation (4D-Var) provides an estimate to the state of a dynamical system through the minimization of a cost functional that measures the distance to a prior state (background) estimate and observations over a time window. The analysis fit to each information input component is determined by the specification of the error covariance matrices in the data assimilation system (DAS). Weak-constraint 4D-Var (w4D-Var) provides a theoretical framework to account for modeling errors in the analysis scheme. In addition to the specification of the background error covariance matrix, the w4D-Var formulation requires information on the model error statistics and …

Normal Surfaces And 3-Manifold Algorithms, Josh D. Hews

Honors Theses

This survey will develop the theory of normal surfaces as they apply to the S3 recognition algorithm. Sections 2 and 3 provide necessary background on manifold theory. Section 4 presents the theory of normal surfaces in triangulations of 3-manifolds. Section 6 discusses issues related to implementing algorithms based on normal surfaces, as well as an overview of the Regina, a program that implements many 3-manifold algorithms. Finally section 7 presents the proof of the 3-sphere recognition algorithm and discusses how Regina implements the algorithm.