2008

最新文章

• Variational inequalities over perturbed polyhedral convex sets AI翻译
  作者：Lu, Shu; Robinson, Stephen M.
  作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of Wisconsin System; University of Wisconsin Madison
  摘要：This paper provides conditions for existence of a locally unique, Lipschitzian solution of a linear variational inequality posed over a polyhedral convex set in R-n under perturbation of either or both of the constant term in the variational inequality and the right-hand side of the system of linear constraints de. ning its feasible set. Conditions for perturbation of just the constant term are well known. Here we show that a suitable extension of those conditions suffices for the more general...
• Asymptotic Behavior of Total Times for Jobs That Must Start Over if a Failure Occurs AI翻译
  作者：Asmussen, Soren; Fiorini, Pierre; Lipsky, Lester; Rolski, Tomasz; Sheahan, Robert
  作者单位：Aarhus University; University of Maine System; University of Southern Maine; University of Connecticut; University of Wroclaw
  摘要：Many processes must complete in the presence of failures. Different systems respond to task failure in different ways. The system may resume a failed task from the failure point (or a saved checkpoint shortly before the failure point), it may give up on the task and select a replacement task from the ready queue, or it may restart the task. The behavior of systems under the first two scenarios is well documented, but the third (RESTART) has resisted detailed analysis. In this paper we derive t...
• Approximate minimization of the regularized expected error over kernel models AI翻译
  作者：Kurkova, Vera; Sanguineti, Marcello
  作者单位：Czech Academy of Sciences; Institute of Computer Science of the Czech Academy of Sciences; University of Genoa
  摘要：Learning from data under constraints on model complexity is studied in terms of rates of approximate minimization of the regularized expected error functional. For kernel models with an increasing number n of kernel functions, upper bounds on such rates are derived. The bounds are of the form a/n+b/root n, where a and b depend on the regularization parameter and on properties of the kernel, and of the probability measure de. ning the expected error. As a special case, estimates of rates of app...
• Finding the Exact Integrality Gap for Small Traveling Salesman Problems AI翻译
  作者：Benoit, Genevieve; Boyd, Sylvia
  作者单位：University of Ottawa
  摘要：The symmetric traveling salesman problem (STSP) is to find a minimum weight Hamiltonian cycle in a weighted complete graph on n nodes. One direction which seems promising for finding improved solutions for the STSP is the study of a linear relaxation of this problem called the subtour elimination problem (SEP). A well-known conjecture in combinatorial optimization says that the integrality gap of the SEP is 4/3 in the metric case. Finding the exact value for this integrality gap is challenging...
• On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games AI翻译
  作者：Dunkel, Juliane; Schulz, Andreas S.
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
  摘要：Rosenthal's congestion games constitute one of the few known classes of noncooperative games possessing pure-strategy Nash equilibria. In the network version, each player wants to route one unit of flow on a single path from her origin to her destination at minimum cost, and the cost of using an arc depends only on the total number of players using that arc. A natural extension is to allow for players controlling different amounts of flow, which results in so-called weighted congestion games. ...
• Separation of nonconvex sets with general augmenting functions AI翻译
  作者：Nedic, Angelia; Ozdaglar, Asuman
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Massachusetts Institute of Technology (MIT)
  摘要：In this paper, we consider two geometric optimization problems that are dual to each other and characterize conditions under which the optimal values of the two problems are equal. This characterization relies on establishing separation results for nonconvex sets using general concave surfaces defined in terms of convex augmenting functions. We prove separation results for augmenting functions that are bounded from below, unbounded augmenting functions, and asymptotic augmenting functions.
• On near optimality of the set of finite-state controllers for average cost POMDP AI翻译
  作者：Yu, Huizhen; Bertsekas, Dimitri P.
  作者单位：University of Helsinki; Massachusetts Institute of Technology (MIT)
  摘要：We consider the average cost problem for partially observable Markov decision processes (POMDP) with finite state, observation, and control spaces. We prove that there exists an E-optimal finite-state controller (FSC) functionally independent of initial distributions for any epsilon > 0, under the assumption that the optimal liminf average cost function of the POMDP is constant. As part of our proof, we establish that if the optimal liminf average cost function is constant, then the optimal li...
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity AI翻译
  作者：Dean, Brian C.; Goemans, Michel X.; Vondrak, Jan
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We consider a stochastic variant of the NP-hard 0/1 knapsack problem, in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution policy that maximizes the expected value of items successfully placed in the knapsack, where the final over. owing item contributes no value. We consider...
• Approximating the GI/GI/1+GI queue with a nonlinear drift diffusion: Hazard rate scaling in heavy traffic AI翻译
  作者：Reed, J. E.; Ward, Amy R.
  作者单位：New York University; University of Southern California
  摘要：We study a single-server queue, operating under the first-in-first-out (FIFO) service discipline, in which each customer independently abandons the queue if his service has not begun within a generally distributed amount of time. Under some mild conditions on the abandonment distribution, we identify a limiting heavy-traffic regime in which the resulting diffusion approximation for both the offered waiting time process ( the process that tracks the amount of time an infinitely patient arriving...
• What matchings can be stable? The testable implications of matching theory AI翻译
  作者：Echenique, Federico
  作者单位：California Institute of Technology
  摘要：This paper studies the falsi. ability of two-sided matching theory when agents' preferences are unknown. A collection of matchings is rationalizable if there are preferences for the agents involved so that the matchings are stable. We show that there are nonrationalizable collections of matchings; hence, the theory is falsi. able. We also characterize the rationalizable collections of matchings, which leads to a test of matching theory in the spirit of revealed-preference tests of individual o...