-
作者：Ben-Tal, Aharon; Nemirovski, Arkadi
作者单位：Technion Israel Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：In the paper we consider the chance-constrained version of an affinely perturbed linear matrix inequality (LMI) constraint, assuming the primitive perturbations to be independent with light-tail distributions (e.g., bounded or Gaussian). Constraints of this type, playing a central role in chance-constrained linear/conic quadratic/semidefinite programming, are typically computationally intractable. The goal of this paper is to develop a tractable approximation to these chance constraints. Our a...
-
作者：Penn, Michal; Polukarov, Maria; Tennenholtz, Moshe
作者单位：Technion Israel Institute of Technology; University of Southampton; Microsoft; MICROSOFT ISRAEL
摘要：We introduce a new class of games called random order congestion games (ROCGs). In an ROCG, each player has a task that can be carried out by any element of a set of resources, and each resource executes its assigned tasks in a random order. The aim of each player is to minimize his expected cost, which is the sum of the fixed costs over the set of his utilized resources and the expected cost of his task execution. The cost of a player's task execution is determined by the earliest time his ta...
-
作者：Buchbinder, Niv; Naor, Joseph (Seffi)
作者单位：Microsoft; Technion Israel Institute of Technology
摘要：We study a wide range of online covering and packing optimization problems. In an online covering problem, a linear cost function is known in advance, but the linear constraints that define the feasible solution space are given one by one, in rounds. In an online packing problem, the profit function as well as the packing constraints are not known in advance. In each round additional information (i.e., a new variable) about the profit function and the constraints is revealed. An online algorit...
-
作者：Salez, Justin; Shah, Devavrat
作者单位：Inria; Universite PSL; Ecole Normale Superieure (ENS); Massachusetts Institute of Technology (MIT)
摘要：The random assignment problem asks for the minimum-cost perfect matching in the complete n x n bipartite graph K-nn with i.i.d. edge weights, say uniform on [0, 1]. In a remarkable work by Aldous [Aldous, D. 2001. The zeta(2) limit in the random assignment problem. RSA 18 381-418], the optimal cost was shown to converge to zeta(2) as n -> infinity, as conjectured by Mezard and Parisi [Mezard, M., G. Parisi. 1987. On the solution of the random link matching problem. J. Phys. 48 1451-1459] throu...
-
作者：Cardaliaguet, Pierre; Rainer, Catherine
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bretagne Occidentale
摘要：For zero-sum two-player continuous-time games with integral payoff and incomplete information on one side, the authors show that the optimal strategy of the informed player can be computed through an auxiliary optimization problem over some martingale measures. The authors also characterize the optimal martingale measures and compute them explicitly in several examples.
-
作者：Qi, Houduo
作者单位：University of Southampton
摘要：Recently, Chan and Sun [Chan, Z. X., D. Sun. Constraint nondegeneracy, strong regularity and nonsingularity in semidefinite programming. SIAM J. Optim. 19 370-376.] reported for semidefinite programming (SDP) that the primal/dual constraint nondegeneracy is equivalent to the dual/primal strong second order sufficient condition (SSOSC). This result is responsible for a number of important results in stability analysis of SDP. In this paper, we study duality of this type in nonlinear semidefinit...
-
作者：Aliev, Iskander; Henk, Martin
作者单位：Cardiff University; Cardiff University; Otto von Guericke University
摘要：The largest integer that cannot be represented as a nonnegative integral combination of given set of positive integers is called the Frobenius number of these integers. We show that the asymptotic growth of the Frobenius number on average is significantly slower than the growth of the maximum Frobenius number.
-
作者：Gurvich, Itay; Whitt, Ward
作者单位：Northwestern University; Columbia University
摘要：Motivated by call centers, we study large-scale service systems with multiple customer classes and multiple agent pools, each with many agents. We propose a family of routing rules called queue-and-idleness-ratio (QIR) rules. A newly available agent next serves the customer from the head of the queue of the class (from among those he is eligible to serve) whose queue length most exceeds a specified state-dependent proportion of the total queue length. An arriving customer is routed to the agen...
-
作者：Teper, Roee
作者单位：Tel Aviv University
摘要：Information consisting of probabilities of some (but possibly not all) events induces an integral with respect to a probability specified on a subalgebra. A decision maker evaluates the alternatives using only the available information and completely ignoring unavailable information. Assume now that the decision maker assesses the worth of a different lottery at each point in a discrete time. Assume also that each such lottery is preferred to some fixed alternative lottery. Now, consider the s...
-
作者：Auslender, Alfred; Goberna, Miguel A.; Lopez, Marco A.
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Ecole Centrale de Lyon; Institut National des Sciences Appliquees de Lyon - INSA Lyon; Universite Claude Bernard Lyon 1; Universite Jean Monnet; Institut Polytechnique de Paris; Ecole Polytechnique; Universitat d'Alacant
摘要：In this paper we consider min-max convex semi-infinite programming. To solve these problems we introduce a unified framework concerning Remez-type algorithms and integral methods coupled with penalty and smoothing methods. This framework subsumes well-known classical algorithms, but also provides some new methods with interesting properties. Convergence of the primal and dual sequences are proved under minimal assumptions.
