-
作者：Deb, S; Shakkottai, S; Srikant, R
作者单位：Alcatel-Lucent; Lucent Technologies; University of Texas System; University of Texas Austin; University of Illinois System; University of Illinois Urbana-Champaign
摘要：Congestion controllers for the Internet are typically designed based on deterministic delay differential equation models. In this paper, we consider the case of a single link accessed by many TCP-like congestion-controlled flows and uncontrolled flows that are modeled as stochastic disturbances. We show that if the number of flows is large and the link capacity is scaled in proportion to the number of users, then under appropriate conditions, the trajectory of the stochastic system is eventual...
-
作者：van der Laan, D
作者单位：Vrije Universiteit Amsterdam
摘要：In this paper we consider the problem of routing deterministic arriving jobs to parallel servers with deterministic (distinct) service times, where we assume that the arrival rate of the jobs is equal to the total service capacity of the servers. Our goal is to find routing policies that minimize the long-run average waiting time of the arriving jobs. We give lower and upper bounds for the minimal long-run average waiting time, and we present results on the structure of optimal policies. We de...
-
作者：Amaldi, E; Hauser, R
作者单位：Polytechnic University of Milan; University of Oxford
摘要：A classical theorem by Block and Levin (Block, H. D., S. A. Levin. 1970. On the boundedness of an iterative procedure for solving a system of linear inequalities. Proc. Amer Math. Soc. 26 229-235) states that certain variants of the relaxation method for solving systems of linear inequalities generate bounded sequences of intermediate solutions, even when applied to infeasible systems. Using a new approach, we prove a more general version of this result and answer an old open problem of quanti...
-
作者：Fleischer, L
作者单位：International Business Machines (IBM); IBM USA; Columbia University
摘要：We give an approximation scheme for separated continuous linear programming problems. Such problems arise as fluid relaxations of multiclass queueing networks and are used to find approximate solutions to complex job shop scheduling problems. In a network with linear flow costs and linear, per-unit-time holding costs, our algorithm finds a drainage of the network that, for given constants epsilon > 0 and delta > 0, has total cost (1 + epsilon)OPT + delta, where OPT is the cost of the minimum c...
-
作者：Schied, A
作者单位：Technical University of Berlin
摘要：This paper introduces a systematic approach to the problem of maximizing the robust utility of the terminal wealth of an admissible strategy in a general complete market model, where the robust utility functional is defined by a set Q of probability measures. Our main result shows that this problem can often be reduced to determining a least favorable measure Q(0) is an element of Q, which is universal in the sense that it does not depend on the particular utility function. The robust problem ...
-
作者：Flores-Bazán, F; López, R
作者单位：Universidad de Concepcion
摘要：In this work we study the classical linear complementarity problem LCP by describing the asymptotic behavior of the approximate solutions to its variational inequality formulation. Thus, some properties satisfied by the directions which are limits of the normalized unbounded approximate solutions will be established. Based on this analysis, various equivalent conditions guaranteeing the existence of solutions to LCP are given. In particular, the sufficient condition of Gowda and Pang expressed...
-
作者：Hordijk, A; van der Laan, D
作者单位：Leiden University - Excl LUMC; Leiden University; Vrije Universiteit Amsterdam
摘要：We consider a deterministic queueing system in which N >= 2 servers of different speeds operate in parallel. Each service in queue i takes the deterministic time S-i. Identical customers arrive exactly one per time unit, and it is desirable to route them to the queues so that the average waiting time (we consider as waiting time the time a customer waits in the buffer of a queue, and thus the service time is not included in this) is minimized. We provide an algorithm to compute lower and upper...
-
作者：Freund, RM; Ordónez, F
作者单位：Massachusetts Institute of Technology (MIT); University of Southern California
摘要：The purpose of this paper is to extend, as much as possible, the modern theory of condition numbers for conic convex optimization: [GRAPHICS] to the more general nonconic format: [GRAPHICS] where P is any closed convex set, not necessarily a cone, which we call the ground-set. Although any convex problem can be transformed to conic form, such transformations are neither unique nor natural given the natural description of many problems, thereby diminishing the relevance of data-based condition ...
-
作者：Oskoorouchi, MR; Goffin, JL
作者单位：California State University System; California State University San Marcos; McGill University; Universite de Montreal
摘要：The convex feasibility problem in general is a problem of finding a point in a convex set that contains a full dimensional ball and is contained in a compact convex set. We assume that the outer set is described by second-order cone inequalities and propose an analytic center cutting plane technique to solve this problem. We discuss primal and dual settings simultaneously. Two complexity results are reported: the complexity of restoration procedure and complexity of the overall algorithm. We p...
-
作者：Bansal, N; Mahdian, M; Sviridenko, M
作者单位：International Business Machines (IBM); IBM USA; Microsoft
摘要：In this paper, we study polynomial time approximation schemes (PTASes) for the no-wait job shop scheduling problem with the makespan objective function. It is known that the problem is MaxSNP-hard in the case when each job is allowed to have three operations or more. We show that if each job has at most two operations, the problem admits a PTAS if the number of machines is a constant (i.e., not part of the input). If the number of machines is not a constant, we show that the problem is hard to...
