-
作者：Chou, MC; Queyranne, M; Simchi-Levi, D
作者单位：National University of Singapore; University of British Columbia; Massachusetts Institute of Technology (MIT)
摘要：Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each running at its own speed, so as to minimize a weighted sum of the job completion times. In this on-line environment, the processing requirement and weight of a job are not known before the job arrives. The Weighted Shortest Processing Requirement (WSPR) heuristic is a simple extension of the well known WSPT heuristic, which is optimal for the single machine problem without release dates. According to...
-
作者：Barahona, F
作者单位：International Business Machines (IBM); IBM USA
摘要：We give an algorithm for the following problem: given a graph G=(V,E) with edge-weights and a nonnegative integer k, find a minimum cost set of edges that contains k disjoint spanning trees. This also solves the following reinforcement problem: given a network, a number k and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains k disjoint spanning trees. The number k is seen as a measure of the invu...
-
作者：Philpott, Andy; Schultz, Ruediger
作者单位：University of Auckland; University of Duisburg Essen
摘要：We consider an electricity generator making offers of energy into an electricity pool market over a horizon of several trading periods (typically a single trading day). The generator runs a set of generating units with given start-up costs, shut-down costs and operating ranges. At the start of each trading period the generator must submit to the pool system operator a new supply curve defining quantities of offered energy and the prices at which it wants these dispatched. The amount of dispatc...
-
作者：Guérin, J; Marcotte, P; Savard, G
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
摘要：Motivated by the study of parametric convex programs, we consider approximation of concave functions by piecewise affine functions. Using dynamic programming, we derive a procedure for selecting the knots at which an oracle provides the function value and one supergradient. The procedure is adaptive in that the choice of a knot is dependent on the choice of the previous knots. It is also optimal in that the approximation error, in the integral sense, is minimized in the worst case.
-
作者：Lasserre, JB
作者单位：Centre National de la Recherche Scientifique (CNRS)
摘要：We consider the optimization problems max (z is an element of Omega) min (x is an element of K) p(z, x) and min (x is an element of K) max (z is an element of Omega) p(z, x) where the criterion p is a polynomial, linear in the variables z, the set Omega can be described by LMIs, and K is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem max (z is an element of Omega) p(z), whereas the second problem is a robust analogue of the generic problem ...
-
作者：Jeyakumar, V
作者单位：University of New South Wales Sydney
摘要：The strong conical hull intersection property ( CHIP) is a geometric property of a collection of finitely many closed convex intersecting sets. This basic property, which was introduced by Deutsch et al. in 1997, is one of the central ingredients in the study of constrained interpolation and best approximation. In this paper we establish that the strong CHIP of intersecting sets of constraints is the key characterizing property for optimality and strong duality of convex programming problems. ...
-
作者：Salazar-González, JJ
作者单位：Universidad de la Laguna
摘要：Rounding methods are common techniques in many statistical offices to protect sensitive information when publishing data in tabular form. Classical versions of these methods do not consider protection levels while searching patterns with minimum information loss, and therefore typically the so-called auditing phase is required to check the protection of the proposed patterns. This paper presents a mathematical model for the whole problem of finding a protected pattern with minimum loss of info...
-
作者：Nesterov, Yurii; Polyak, B. T.
作者单位：Universite Catholique Louvain; V.A. Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
摘要：In this paper, we provide theoretical analysis for a cubic regularization of Newton method as applied to unconstrained minimization problem. For this scheme, we prove general local convergence results. However, the main contribution of the paper is related to global worst-case complexity bounds for different problem classes including some nonconvex cases. It is shown that the search direction can be computed by standard linear algebra technique.
-
作者：Dyer, M; Stougie, L
作者单位：University of Leeds; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
摘要：Stochastic programming is the subfield of mathematical programming that considers optimization in the presence of uncertainty. During the last four decades a vast quantity of literature on the subject has appeared. Developments in the theory of computational complexity allow us to establish the theoretical complexity of a variety of stochastic programming problems studied in this literature. Under the assumption that the stochastic parameters are independently distributed, we show that two-sta...
-
作者：Bonomo, F; Durán, G; Lin, MC; Szwarcfiter, JL
作者单位：University of Buenos Aires; Universidad de Chile; Universidade Federal do Rio de Janeiro; Universidade Federal do Rio de Janeiro
摘要：Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomia...
