-
作者：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.
-
作者：Sanders, Peter; Sivadasan, Naveen; Skutella, Martin
作者单位：Helmholtz Association; Karlsruhe Institute of Technology; Max Planck Society; Technical University of Berlin
摘要：Consider the classical online scheduling problem, in which jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by some constant times the size of the arriving job. This constant is called the migration factor. For small migration factors, we obtain several...
-
作者：Olszewski, Wojciech; Sandroni, Alvaro
作者单位：Northwestern University; University of Pennsylvania; Northwestern University
摘要：Theories can be produced by experts seeking a reputation for having knowledge. Hence, a tester could anticipate that theories may have been strategically produced by uninformed experts who want to pass an empirical test. We show that, with no restriction on the domain of permissible theories, strategic experts cannot be discredited for an arbitrary but given number of periods, no matter which test is used (provided that the test does not reject the actual data-generating process). Natural ways...
-
作者：Ding, Yichuan; Wolkowicz, Henry
作者单位：Stanford University; University of Waterloo
摘要：The quadratic assignment problem (QAP) is arguably one of the hardest NP-hard discrete optimization problems. Problems of dimension greater than 25 are still considered to be large scale. Current successful solution techniques use branch-and-bound methods, which rely on obtaining strong and inexpensive bounds. In this paper, we introduce a new semidefinite programming (SDP) relaxation for generating bounds for the QAP in the trace formulation. We apply majorization to obtain a relaxation of th...
-
作者：Conforti, Michele; Di Summa, Marco; Eisenbrand, Friedrich; Wolsey, Laurence A.
作者单位：University of Padua; Universite Catholique Louvain; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider mixed-integer sets described by system of linear inequalities in which the constraint matrix A is totally unimodular; the right-hand side is arbitrary vector; and a subset of the variables is required to be integer. We show that the problem of checking nonemptiness of a set of this type is NP-complete, even in the case in which the linear system describes mixed-integer network flows with half-integral requirement on the nodes. This is in contrast to the case in which A is totally u...
-
作者：Huh, Woonghee Tim; Rusmevichientong, Paat
作者单位：Columbia University; Cornell University
摘要：We study stochastic inventory planning with lost sales and instantaneous replenishment where, contrary to the classical inventory theory, knowledge of the demand distribution is not available. Furthermore, we observe only the sales quantity in each period and lost sales are unobservable, that is, demand data are censored. The manager must make an ordering decision in each period based only on historical sales data. Excess inventory is either perishable or carried over to the next period. In th...
