Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(Generalized Binary Search). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


The Ohio State University

1. Huang, Shijie. Waiting Lines and System Selection in Constrained Service Systems with Applications in Election Resource Allocation.

Degree: PhD, Industrial and Systems Engineering, 2016, The Ohio State University

In the United States, voting is one of the most fundamental rights protected by the federal law. However, there is a growing concern over voter disenfranchisement and system inequity caused by long waiting lines. Studies have found that inappropriate voting resource allocation has deterred hundreds of thousands of U.S. citizens from voting. This research proposes an analytic framework to quantify the number of deterred voters and assess the resulting political consequences. We apply this framework to the 2012 Sandoval County General Election in New Mexico to study whether electoral outcomes were altered by “effective disenfranchisement” for a few closely contested offices. Furthermore, Indifference-Zone Generalized Binary Search (IZGBS) is developed to determine the minimum sets of resources needed to satisfy a given service level for elections with one or multiple bottleneck resources. What makes the problem challenging is the service level generally needs to be evaluated using discrete event simulations, which is slow and noisy. For example, there are no analytical methods to estimate the waiting time of the 99th percentile voter. Thus, simulation-based ranking and selection (R&S), also known as design and analysis of R&S experiments, are preferred than stochastic integer programming methods in this type of problems. The proposed approach incorporates constrained R&S with Generalized Binary Search (GBS) to provide computationally efficient and rigorous solutions. It also explores the intuitive monotone assumption that adding resources cannot harm average performance for relevant Discrete Event Simulation (DES) models, which has received little attention in the simulation literature previously.The method is based on the assumption of normal populations (but not requiring equal variances). Therefore, special attention is given to quantile-related outputs that are associated with asymptotically normal estimates. The asymptote is in the number of simulated voters on Election Day, which is often over one thousand. Later, IZGBS is applied to the Franklin County of Ohio and Sandoval County of New Mexico to establish the resource requirement so that voters can expect to wait less than thirty minutes. Several topics are suggested for future research, including building on IZGBS to provide optimization solutions for more general problems. Advisors/Committee Members: Allen, Theodore (Advisor).

Subjects/Keywords: Industrial Engineering; Operations Research; Multiple Comparisons; Comparison with a Standard; Ranking and Selection; Indifference-zone; Generalized Binary Search; Simulation-based Optimization; Quantile Estimator; Election; Voting System; Equity

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Huang, S. (2016). Waiting Lines and System Selection in Constrained Service Systems with Applications in Election Resource Allocation. (Doctoral Dissertation). The Ohio State University. Retrieved from http://rave.ohiolink.edu/etdc/view?acc_num=osu1471541297

Chicago Manual of Style (16th Edition):

Huang, Shijie. “Waiting Lines and System Selection in Constrained Service Systems with Applications in Election Resource Allocation.” 2016. Doctoral Dissertation, The Ohio State University. Accessed November 26, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=osu1471541297.

MLA Handbook (7th Edition):

Huang, Shijie. “Waiting Lines and System Selection in Constrained Service Systems with Applications in Election Resource Allocation.” 2016. Web. 26 Nov 2020.

Vancouver:

Huang S. Waiting Lines and System Selection in Constrained Service Systems with Applications in Election Resource Allocation. [Internet] [Doctoral dissertation]. The Ohio State University; 2016. [cited 2020 Nov 26]. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1471541297.

Council of Science Editors:

Huang S. Waiting Lines and System Selection in Constrained Service Systems with Applications in Election Resource Allocation. [Doctoral Dissertation]. The Ohio State University; 2016. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1471541297

2. Bellala, Gowtham. Information and Decision Theoretic Approaches to Problems in Active Diagnosis.

Degree: PhD, Electrical Engineering: Systems, 2012, University of Michigan

In applications such as active learning or disease/fault diagnosis, one often encounters the problem of identifying an unknown object while minimizing the number of ``yes" or ``no" questions (queries) posed about that object. This problem has been commonly referred to as object/entity identification or active diagnosis in the literature. In this thesis, we consider several extensions of this fundamental problem that are motivated by practical considerations in real-world, time-critical identification tasks such as emergency response. First, we consider the problem where the objects are partitioned into groups, and the goal is to identify only the group to which the object belongs. We then consider the case where the cost of identifying an object grows exponentially in the number of queries. To address these problems we show that a standard algorithm for object identification, known as the splitting algorithm or generalized binary search (GBS), may be viewed as a generalization of Shannon-Fano coding. We then extend this result to the group-based and the exponential cost settings, leading to new, improved algorithms. We then study the problem of active diagnosis under persistent query noise. Previous work in this area either assumed that the noise is independent or that the underlying query noise distribution is completely known. We make no such assumptions, and introduce an algorithm that returns a ranked list of objects, such that the expected rank of the true object is optimized. Finally, we study the problem of active diagnosis where multiple objects are present, such as in disease/fault diagnosis. Current algorithms in this area have an exponential time complexity making them slow and intractable. We address this issue by proposing an extension of our rank-based approach to the multiple object scenario, where we optimize the area under the ROC curve of the rank-based output. The AUC criterion allows us to make a simplifying assumption that significantly reduces the complexity of active diagnosis (from exponential to near quadratic), with little or no compromise on the performance quality. Further, we demonstrate the performance of the proposed algorithms through extensive experiments on both synthetic and real world datasets. Advisors/Committee Members: Scott, Clayton D. (committee member), Hero Iii, Alfred O. (committee member), Murphy, Susan A. (committee member), Sadanandarao, Sandeep P. (committee member).

Subjects/Keywords: Machine Learning; Active Diagnosis; Active Learning; Object/Entity Identification; Bayesian Networks; Generalized Binary Search; Computer Science; Electrical Engineering; Engineering

generalized binary search (GBS), may be viewed as a generalization of Shannon-Fano coding… …algorithm, or generalized binary search (GBS) to these settings. The proposed algorithms… …generalized binary search (GBS) (Dasgupta, 2004; Nowak , 2008). This algorithm… …binary search) as a generalized form of Shannon-Fano coding. We first establish an exact… …x29; object/entity identification (Garey, 1970, 1972), and binary testing (… 

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Bellala, G. (2012). Information and Decision Theoretic Approaches to Problems in Active Diagnosis. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/91606

Chicago Manual of Style (16th Edition):

Bellala, Gowtham. “Information and Decision Theoretic Approaches to Problems in Active Diagnosis.” 2012. Doctoral Dissertation, University of Michigan. Accessed November 26, 2020. http://hdl.handle.net/2027.42/91606.

MLA Handbook (7th Edition):

Bellala, Gowtham. “Information and Decision Theoretic Approaches to Problems in Active Diagnosis.” 2012. Web. 26 Nov 2020.

Vancouver:

Bellala G. Information and Decision Theoretic Approaches to Problems in Active Diagnosis. [Internet] [Doctoral dissertation]. University of Michigan; 2012. [cited 2020 Nov 26]. Available from: http://hdl.handle.net/2027.42/91606.

Council of Science Editors:

Bellala G. Information and Decision Theoretic Approaches to Problems in Active Diagnosis. [Doctoral Dissertation]. University of Michigan; 2012. Available from: http://hdl.handle.net/2027.42/91606

.