-
作者：Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
作者单位：Carnegie Mellon University; University of Michigan System; University of Michigan; Carnegie Mellon University
摘要：We consider the problem of constructing optimal decision trees: given a collection of tests that can disambiguate between a set of m possible diseases, each test having a cost, and the a priori likelihood of any particular disease, what is a good adaptive strategy to perform these tests to minimize the expected cost to identify the disease? This problem has been studied in several works, with O(log m)-approximations known in the special cases when either costs or probabilities are uniform. In ...
-
作者：Ying, Lei; Srikant, R.; Kang, Xiaohan
作者单位：Arizona State University; Arizona State University-Tempe; University of Illinois System; University of Illinois Urbana-Champaign
摘要：In many computing and networking applications, arriving tasks have to be routed to one of many servers, with the goal of minimizing queueing delays. When the number of processors is very large, a popular routing algorithm works as follows: select two servers at random and route an arriving task to the least loaded of the two. It is well known that this algorithm dramatically reduces queueing delays compared to an algorithm, which routes to a single randomly selected server. In recent cloud com...
-
作者：Suk, Tonghoon; Shin, Jinwoo
作者单位：International Business Machines (IBM); IBM USA; Korea Advanced Institute of Science & Technology (KAIST)
摘要：Ever since Tassiulas and Ephremides in 1992 proposed the maximum weight scheduling algorithm of throughput optimality for constrained queueing networks that arise in the context of communication networks, extensive efforts have been devoted to resolving its most important drawback: high complexity. This paper proposes a generic framework for designing throughput-optimal and low-complexity scheduling algorithms for constrained queueing networks. Under our framework, a scheduling algorithm updat...
-
作者：Belomestny, Denis; Kraetschmer, Volker
作者单位：University of Duisburg Essen; Russian Academy of Sciences
摘要：In this paper we study optimal stopping problems with respect to distorted expectations with concave distortion functions. Our starting point is a seminal work of Xu and Zhou in 2013, who gave an explicit solution of such a stopping problem under a rather large class of distortion functionals. In this paper, we continue this line of research and prove a novel representation, which relates the solution of an optimal stopping problem under distorted expectation to the sequence of standard optima...
