2期

最新文章

• A Randomly Weighted Minimum Arborescence with a Random Cost Constraint AI翻译
  作者：Frieze, Alan M.; Tkocz, Tomasz
  作者单位：Carnegie Mellon University
  摘要：We study the minimum spanning arborescence problem on the complete digraph (K) over right arrow (n), where an edge e has a weight W-e and a cost C-e, each of which is an independent uniform random variable U-s, where 0 < s <= 1 and U is uniform [0,1]. There is also a constraint that the spanning arborescence T must satisfy C(T) <= c(0). We establish, for a range of values for c(0),s, the asymptotic value of the optimum weight via the consideration of a dual problem.
• Multivariate Monotone Inclusions in Saddle Form AI翻译
  作者：Bui, Minh N.; Combettes, Patrick L.
  作者单位：North Carolina State University
  摘要：We propose a novel approach to monotone operator splitting based on the notion of a saddle operator. Under investigation is a highly structured multivariate monotone inclusion problem involving a mix of set-valued, cocoercive, and Lipschitzian monotone operators, as well as various monotonicity-preserving operations among them. This model encompasses most formulations found in the literature. A limitation of existing primal-dual algorithms is that they operate in a product space that is too sm...
• Geometrically Convergent Simulation of the Extrema of Levy Processes AI翻译
  作者：Gonzalez Cazares, Jorge Ignacio; Mijatovic, Aleksandar; Uribe Bravo, Geronimo
  作者单位：Alan Turing Institute; University of Warwick; Universidad Nacional Autonoma de Mexico
  摘要：We develop a novel approximate simulation algorithm for the joint law of the position, the running supremum, and the time of the supremum of a general Levy process at an arbitrary finite time. We identify the law of the error in simple terms. We prove that the error decays geometrically in L-p (for any p >= 1) as a function of the computational cost, in contrast with the polynomial decay for the approximations available in the literature. We establish a central limit theorem and construct nona...
• Strong Embeddings for Transitory Queueing Models AI翻译
  作者：Chakraborty, Prakash; Honnappa, Harsha
  作者单位：Purdue University System; Purdue University; Purdue University System; Purdue University
  摘要：In this paper, we establish strong embedding theorems, in the sense of the Komlos-Major-Tusnady framework, for the performance metrics of a general class of transitory queueing models of nonstationary queueing systems. The nonstationary and non-Markovian nature of these models makes the computation of performance metrics hard. The strong embeddings yield error bounds on sample path approximations by diffusion processes in the formof functional strong approximation theorems.
• Coupled Learning Enabled Stochastic Programming with Endogenous Uncertainty AI翻译
  作者：Liu, Junyi; Li, Guangyu; Sen, Suvrajeet
  作者单位：Tsinghua University; University of Southern California; University of Southern California
  摘要：Predictive analytics, empowered by machine learning, is usually followed by decision-making problems in prescriptive analytics. We extend the previous sequential prediction-optimization paradigm to a coupled scheme such that the prediction model can guide the decision problem to produce coordinated decisions yielding higher levels of performance. Specifically, for stochastic programming (SP) models with latently decision-dependent uncertainty, without any parametric assumption of the latent de...
• M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System AI翻译
  作者：Shioura, Akiyoshi
  作者单位：Institute of Science Tokyo; Tokyo Institute of Technology
  摘要：In this paper, we consider a problem of minimizing an M-convex function under an L1-distance constraint (MML1); the constraint is given by an upper bound for L1-distance between a feasible solution and a given center. This is motivated by a nonlinear integer programming problem for reallocation of dock capacity in a bike-sharing system discussed by Freund et al. (2017). The main aim of this paper is to better understand the combinatorial structure of the dock reallocation problem through the c...
• Large Fork-Join Queues with Nearly Deterministic Arrival and Service Times AI翻译
  作者：Schol, Dennis; Vlasiou, Maria; Zwart, Bert
  作者单位：Eindhoven University of Technology; University of Twente
  摘要：In this paper, we study an N server fork-join queue with nearly deterministic arrival and service times. Specifically, we present a fluid limit for the maximum queue length as N -> infinity. This fluid limit depends on the initial number of tasks. In order to prove these results, we develop extreme value theory and diffusion approximations for the queue lengths.
• Multiplayer Bandits Without Observing Collision Information AI翻译
  作者：Lugosi, Gabor; Mehrabian, Abbas
  作者单位：Pompeu Fabra University; ICREA; McGill University
  摘要：We study multiplayer stochastic multiarmed bandit problems in which the players cannot communicate, and if two or more players pull the same arm, a collision occurs and the involved players receive zero reward. We consider two feedback models: a model in which the players can observe whether a collision has occurred and a more difficult setup in which no collision information is available. We give the first theoretical guarantees for the second model: an algorithm with a logarithmic regret and...
• Sufficiency of Markov Policies for Continuous-Time Jump Markov Decision Processes AI翻译
  作者：Feinberg, Eugene A.; Mandava, Manasa; Shiryaev, Albert N.
  作者单位：State University of New York (SUNY) System; Stony Brook University; Indian School of Business (ISB); Russian Academy of Sciences; Steklov Mathematical Institute of the Russian Academy of Sciences
  摘要：One of the basic facts known for discrete-time Markov decision processes is that, if the probability distribution of an initial state is fixed, then for every policy it is easy to construct a (randomized) Markov policy with the same marginal distributions of state-action pairs as for the original policy. This equality of marginal distributions implies that the values of major objective criteria, including expected discounted total costs and average rewards per unit time, are equal for these tw...
• Coordination Games on Weighted Directed Graphs AI翻译
  作者：Apt, Krzysztof R.; Simon, Sunil; Wojtczak, Dominik
  作者单位：University of Warsaw; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Kanpur; University of Liverpool
  摘要：We study strategic games on weighted directed graphs, where each player's payoff is defined as the sum of the weights on the edges from players who chose the same strategy, augmented by a fixed nonnegative integer bonus for picking a given strategy. These games capture the idea of coordination in the absence of globally common strategies. We identify natural classes of graphs for which finite improvement or coalition-improvement paths of polynomial length always exist, and consequently a (pure...