Embedded Files
UN Sustainability Development Goals
UN Sustainability Development Goals
This research advances the UN's Sustainable Development Goal 9: Industry, Innovation, and Infrastructure. Stochastic function evaluation problems can be more broadly classified under stochastic optimization. Algorithms for stochastic optimization have applications in areas such as optimizing sensor placement, computational biology, efficient ballot counting, sequential diagnostic testing, and cybersecurity.
NYU Tandon Impact Areas
NYU Tandon Impact Areas
This research falls under NYU Tandon's System Engineering and Complex Decision-Making Impact Area, as its focus is on algorithms for decision-making under uncertainty.
Poster
Poster
Abstract
Abstract
Many situations require performing pre-defined actions sequentially in order to answer a question of interest. For example, a doctor may have a range of medical tests available, each with potential informative value towards some diagnosis; a rescue operation may have a set of possible locations to search to determine the number of survivors that can be saved; antivirus software analyzing a potentially malicious program may have numerous sections of code it could test to determine the program’s safety. In these types of situations, the question naturally arises: what ordering minimizes the expected number of necessary actions? Mathematically abstracted from a range of distinct but related applications, these situations are classified as stochastic sequence ordering (SSO) problems. Our research focuses on the design of algorithms for SSO problems. We have two criteria for an SSO algorithm, which must be provably met under any possible input: it must run efficiently with respect to the problem’s size, and it must produce a strategy which is either exactly or approximately optimal. If an algorithm’s ordering is guaranteed to require at most, in expectation, k times the number of actions as the optimal ordering, the algorithm is a k-approximation algorithm. We present an O(log Q)-approximation algorithm for nonadaptively evaluating any discrete function of independent stochastic inputs, where Q is a measure of the complexity of the function in question known as its goal value. We apply this result to the problem of evaluating the Coupon Counting Function, obtaining an O(log d)-approximation algorithm, where d is the number of coupons. We generalize this to a closely related but more difficult function, the Coupon Collection Function, to obtain a max{O(log d), n/(n - d + 2)}-approximation algorithm. We also present a 1-additive approximation algorithm for evaluating the related d-ary Unanimous Vote Function.
Many situations require performing pre-defined actions sequentially in order to answer a question of interest. For example, a doctor may have a range of medical tests available, each with potential informative value towards some diagnosis; a rescue operation may have a set of possible locations to search to determine the number of survivors that can be saved; antivirus software analyzing a potentially malicious program may have numerous sections of code it could test to determine the program’s safety. In these types of situations, the question naturally arises: what ordering minimizes the expected number of necessary actions? Mathematically abstracted from a range of distinct but related applications, these situations are classified as stochastic sequence ordering (SSO) problems. Our research focuses on the design of algorithms for SSO problems. We have two criteria for an SSO algorithm, which must be provably met under any possible input: it must run efficiently with respect to the problem’s size, and it must produce a strategy which is either exactly or approximately optimal. If an algorithm’s ordering is guaranteed to require at most, in expectation, k times the number of actions as the optimal ordering, the algorithm is a k-approximation algorithm. We present an O(log Q)-approximation algorithm for nonadaptively evaluating any discrete function of independent stochastic inputs, where Q is a measure of the complexity of the function in question known as its goal value. We apply this result to the problem of evaluating the Coupon Counting Function, obtaining an O(log d)-approximation algorithm, where d is the number of coupons. We generalize this to a closely related but more difficult function, the Coupon Collection Function, to obtain a max{O(log d), n/(n - d + 2)}-approximation algorithm. We also present a 1-additive approximation algorithm for evaluating the related d-ary Unanimous Vote Function.
Final Paper
Final Paper
Su25_write_up_new.pdfPage updated
Report abuse