2期

最新文章

• Delay Analysis of the Max-Weight Policy Under Heavy-Tailed Traffic via Fluid Approximations AI翻译
  作者：Markakis, Mihalis G.; Modiano, Eytan; Tsitsiklis, John N.
  作者单位：Pompeu Fabra University; Massachusetts Institute of Technology (MIT)
  摘要：We consider switched queueing networks with a mix of heavy-tailed (i.e., arrival processes with infinite variance) and exponential-type traffic and study the delay performance of the max-weight policy, known for its throughput optimality and asymptotic delay optimality properties. Our focus is on the impact of heavy-tailed traffic on exponential-type queues/flows, which may manifest itself in the form of subtle rate-dependent phenomena. We introduce a novel class of Lyapunov functions (piecewi...
• Opposite Elements in Clutters AI翻译
  作者：Abdi, Ahmad; Fukasawa, Ricardo; Sanita, Laura
  作者单位：University of Waterloo
  摘要：Let E be a finite set of elements, and let L be a clutter over ground set E. We say distinct elements e, f are opposite if every member and every minimal cover of L contains at most one of e, f . In this paper, we investigate opposite elements and reveal a rich theory underlying such a seemingly simple restriction. The clutter C obtained from L after identifying some opposite elements is called an identification of L; inversely, L is called a split of C. We will show that splitting preserves t...
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem AI翻译
  作者：Feldman, Moran; Svensson, Ola; Zenklusen, Rico
  作者单位：Open University Israel; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Swiss Federal Institutes of Technology Domain; ETH Zurich
  摘要：Only recently, progress has been made in obtaining o(log(rank))-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a O((log(rank))(1/2))-competitive procedure, and Lachish (2014) later presented a O(log log(rank))-competitive algorithm. Both these algorithms and their analyses are very involved, which is also reflected in the extremely high constants in their competitive ratios. Using different tools, we present a considerably sim...
• Nonzero-Sum Risk-Sensitive Stochastic Games on a Countable State Space AI翻译
  作者：Basu, Arnab; Ghosh, Mrinal K.
  作者单位：Indian Institute of Management (IIM System); Indian Institute of Management Bangalore; Indian Institute of Science (IISC) - Bangalore
  摘要：The infinite horizon risk-sensitive discounted-cost and ergodic-cost nonzero-sum stochastic games for controlled Markov chains with countably many states are analyzed. For the discounted-cost game, we prove the existence of Nash equilibrium strategies in the class of Markov strategies under fairly general conditions. Under an additional weak geometric ergodicity condition and a small cost criterion, the existence of Nash equilibrium strategies in the class of stationary Markov strategies is pr...
• Workload-Dependent Dynamic Priority for the Multiclass Queue with Reneging AI翻译
  作者：Atar, Rami; Lev-Ari, Anat
  作者单位：Technion Israel Institute of Technology
  摘要：Scheduling control for a single-server queue with I customer classes and reneging is considered, with linear holding or reneging cost. An asymptotically optimal (AO) policy in heavy traffic is identified where classes are prioritized according to a workload-dependent dynamic index rule. Denote by c(i), mu(i), and theta(i), i is an element of J := {1, . . . , I} the queue length cost, service rate, and reneging rate, for class-i customers. Then, a relabeling of the classes and a partition 0 = w...
• The Complexity of Simple Models-A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem AI翻译
  作者：Bomze, Immanuel M.; Schachinger, Werner; Ullrich, Reinhard
  作者单位：University of Vienna
  摘要：In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite this simplicity, the nonconvex instances of this problem class allow for remarkably rich patterns of coexisting local solutions, which is closely related to practical difficulties in solving StQPs globally. In this study, we improve on existing lower bounds for the number of strict local solutions by ...
• Robust Randomized Matchings AI翻译
  作者：Matuschke, Jannik; Skutella, Martin; Soto, Jose A.
  作者单位：Technical University of Munich; Technical University of Munich; Technical University of Berlin; Universidad de Chile; Universidad de Chile
  摘要：The following game is played on a weighted graph: Alice selects a matching M and Bob selects a number k. Alice's payoff is the ratio of the weight of the k heaviest edges of M to the maximum weight of a matching of size at most k. If M guarantees a payoff of at least a then it is called alpha-robust. In 2002, Hassin and Rubinstein gave an algorithm that returns a 1/root 2 -robust matching, which is best possible. We show that Alice can improve her payoff to 1/ln(4) by playing a randomized stra...
• Risk-Averse Approximate Dynamic Programming with Quantile-Based Risk Measures AI翻译
  作者：Jiang, Daniel R.; Powell, Warren B.
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Princeton University
  摘要：In this paper, we consider a finite-horizon Markov decision process (MDP) for which the objective at each stage is to minimize a quantile-based risk measure (QBRM) of the sequence of future costs; we call the overall objective a dynamic quantile-based risk measure (DQBRM). In particular, we consider optimizing dynamic risk measures where the one-step risk measures are QBRMs, a class of risk measures that includes the popular value at risk (VaR) and the conditional value at risk (CVaR). Althoug...
• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming AI翻译
  作者：Han, Deren; Sun, Defeng; Zhang, Liwei
  作者单位：Nanjing Normal University; Hong Kong Polytechnic University; Dalian University of Technology
  摘要：In this paper, we aim to prove the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a mild calmness condition, which holds automatically for convex composite piecewise linear-quadratic programming, we establish the global Q-linear rate of convergence for a general semi-proximal ADMM with the dual step-length being taken in (0, (1 + 5(1/2))/2). This semi-proximal ADMM, which covers th...
• Minimizing Piecewise-Concave Functions Over Polyhedra AI翻译
  作者：Gaudioso, Manlio; Giallombardo, Giovanni; Miglionico, Giovanna
  作者单位：University of Calabria
  摘要：We introduce an iterative method for solving linearly constrained optimization problems, whose nonsmooth nonconvex objective function is defined as the pointwise maximum of finitely many concave functions. Such problems often arise from reformulations of certain constraint structures (e.g., binary constraints, finite max-min constraints) in diverse areas of optimization. We state a local optimization strategy, which exploits piecewise-concavity of the objective function, giving rise to a linea...