-
作者：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...
-
作者：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...
-
作者：Borst, S; Zwart, B
作者单位：Centrum Wiskunde & Informatica (CWI); Alcatel-Lucent; Lucent Technologies; AT&T; Eindhoven University of Technology
摘要：We consider a fluid queue fed by several heterogeneous M/G/infinity input processes with regularly varying session lengths. Under fairly mild assumptions, we derive the exact asymptotic behavior of the stationary workload distribution. In addition, we obtain several asymptotic results for the transient workload distribution, which are applied to obtain a conditional limit theorem for the most probable time to overflow. The results are strongly inspired by the large-deviations idea that overflo...
-
作者：Chen, XJ; Fukushima, M
作者单位：Hirosaki University; Kyoto University
摘要：This paper presents a new formulation for the stochastic linear complementarity problem (SLCP), which aims at minimizing an expected residual defined by an NCP function. We generate observations by the quasi-Monte Carlo methods and prove that every accumulation point of minimizers of discrete approximation problems is a minimum expected residual solution of the SLCP. We show that a sufficient condition for the existence of a solution to the expected residual minimization (ERM) problem and its ...
-
作者：Tao, JY; Gowda, MS
作者单位：Loyola University Maryland; University System of Maryland; University of Maryland Baltimore County
摘要：In this article, we introduce the concepts of P and P-0 properties for a nonlinear transformation defined on a Euclidean Jordan algebra and study existence of solution in the associated complementarity problems. In particular, we show, in this general setting, that if a transformation has the P-0 and R-0 properties, then all associated complementarity problems have solutions. We also describe a necessary condition for a transformation to have Lie (global) uniqueness of solution property.
-
作者：Mordukhovich, BS; Nam, NM
作者单位：Wayne State University
摘要：Robust Lipschitzian properties of set-valued mappings and marginal functions play a crucial role in many aspects of variational analysis and its applications, especially for issues related to variational stability and optimization. We develop an approach to variational stability based on generalized differentiation. The principal achievements of this paper include new results on coderivative calculus for set-valued mappings and singular subdifferentials of marginal functions in infinite dimens...
-
作者：Alvarez, F; Carrasco, M; Pichard, K
作者单位：Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile
摘要：In order to minimize a closed convex function that is approximated by a sequence of better behaved functions, we investigate the global convergence of a general hybrid iterative algorithm, which consists of an inexact relaxed proximal point step followed by a suitable orthogonal projection onto a hyperplane. The latter permits to consider a fixed relative error criterion for the proximal step. We provide various sets of conditions ensuring the global convergence of this algorithm. The analysis...
-
作者：Einstein, O; Hassin, R
作者单位：Tel Aviv University; Tel Aviv University
摘要：This paper deals with families of optimization problems defined over a common set of potential solutions. We consider several problems-solutions systems, and for each one, prove the existence of a small set of solutions that contains an optimal solution to every problem. These proofs are mostly algebraic in nature. The families of problems covered here mostly include separation problems, problems on graphs and hypergraphs, and SAT problems.
