-
作者：Davis, Chad; Hare, Warren
作者单位：University of British Columbia
摘要：The normal cone to a constraint set plays a key role in optimization theory, algorithms, and applications. We consider the question of how to approximate the normal cone to a set under the assumption that the set is provided through an oracle function or collection of oracle functions, but contains some exploitable structure. We provide a new simplex gradient-based approximation technique that works for sets defined through a finite number of oracle-based functions. We further present novel re...
-
作者：Tomala, Tristan
作者单位：Hautes Etudes Commerciales (HEC) Paris
摘要：This paper considers a general model of repeated games with incomplete information and imperfect monitoring. We study belief-free communication equilibria (BFCE) defined as follows. Players communicate with. a mediator who receives types and signals and recommends actions. A BFCE is a communication device such that all players have an incentive to play faithfully, irrespectively of their belief about the state. We characterize BFCE payoffs for any repeated game with incomplete information in t...
-
作者：Blanchet, Jose
作者单位：Columbia University
摘要：We consider the problems of computing overflow probabilities at level N in any subset of stations in a Jackson network and of simulating sample paths conditional on overflow. We construct algorithms that take O(N) function evaluations to estimate such overflow probabilities within a prescribed relative accuracy and to simulate paths conditional on overflow at level N. The algorithms that we present are optimal in the sense that the best possible performance that can be expected for conditional...
-
作者：Dieker, A. B.; Shin, J.
作者单位：University System of Georgia; Georgia Institute of Technology; International Business Machines (IBM); IBM USA
摘要：We construct a generic, simple, and efficient scheduling policy for stochastic processing networks, and provide a general framework to establish its stability. Our policy is randomized and prioritized: with high probability it prioritizes jobs that have been least routed through the network. We show that the network is globally stable under this policy if there exists an appropriate quadratic local Lyapunov function that provides a negative drift with respect to nominal loads at servers. Apply...
-
作者：Hoshino, Richard; Kawarabayashi, Ken-ichi
作者单位：Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; Japan Science & Technology Agency (JST)
摘要：The bipartite traveling tournament problem (BTTP) is an NP-complete scheduling problem whose solution is a double round-robin inter-league tournament with minimum total travel distance. The 2n-team BTTP is a variant of the well-known traveling salesman problem (TSP), albeit much harder as it involves the simultaneous coordination of 2n teams playing a sequence of home and away games under fixed constraints, rather than a single entity passing through the locations corresponding to the teams' h...
-
作者：Wang, C. Y.; Yang, X. Q.; Yang, X. M.
作者单位：Qufu Normal University; Hong Kong Polytechnic University; Chongqing Normal University
摘要：In this paper, a unified framework of a nonlinear augmented Lagrangian dual problem is investigated for the primal problem of minimizing an extended real-valued function by virtue of a nonlinear augmenting penalty function. Our framework is more general than the ones in the literature in the sense that our nonlinear augmenting penalty function is defined on an open set and that our assumptions are presented in terms of a substitution of the dual variable, so our scheme includes barrier penalty...
-
作者：Ghamami, Samim; Ward, Amy R.
作者单位：University of California System; University of California Berkeley; University of Southern California
摘要：We consider a dynamic control problem for a parallel server system commonly known as the N-system. An N-system is a two-server parallel server system with two job classes, one server that can serve both classes, and one server that can only serve one class. We assume that jobs within each class arrive according to a renewal process. The random service time of a job has a general distribution that may depend on both the job's class and the server providing the service. Each job independently re...
-
作者：Pai, Mallesh M.; Vohra, Rakesh
作者单位：University of Pennsylvania; Northwestern University
摘要：A monopolist seller has multiple units of an indivisible good to sell over a discrete, finite time horizon. Buyers with unit demand arrive over time and each buyer privately knows her arrival time, her value for a unit, and her deadline. We study whether the seller's optimal allocation rule is a simple index rule. Each buyer is assigned an index and the allocation rule is calculated by a dynamic knapsack algorithm using those indices. Simple indicates that the index of a buyer depends only on ...
-
作者：Davis, Chad; Hare, Warren
-
作者：Kulik, Ariel; Shachnai, Hadas; Tamir, Tami
作者单位：Technion Israel Institute of Technology; Reichman University
摘要：Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location, and marketing over social networks. In this paper we consider the problem of maximizing any submodular function subject to d knapsack constraints, where d is a fixed constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through extension by expectation of the ...
