-
作者：Ye, Jane J.
作者单位：University of Victoria
摘要：In this paper we consider the bilevel programming problem (BLPP), which is a sequence of two optimization problems where the constraint region of the upper-level problem is determined implicitly by the solution set to the lower-level problem. We extend well-known constraint qualifications for nonlinear programming problems such as the Abadie constraint qualification, the Kuhn-Tucker constraint qualification, the Zangwill constraint qualification, the Arrow-Hurwicz-Uzawa constraint qualificatio...
-
作者：Megow, Nicole; Uetz, Marc; Vredeveld, Tjark
作者单位：Technical University of Berlin; Maastricht University
摘要：We consider a model for scheduling under, uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both stochastic scheduling and online scheduling as a special case. The particular s...
-
作者：Bansal, Nikhil; Kimbrel, Tracy; Sviridenko, Maxim
作者单位：International Business Machines (IBM); IBM USA
摘要：We consider randomized algorithms for the preemptive job shop problem, or equivalently, the case in which all operations have unit length. We give an a-approximation for the case of two machines where alpha < 1.45, an improved approximation ratio of O(log m/log log m) for an arbitrary number m of machines, and the first (2 + epsilon) -approximation for a constant number of machines. The first result is via an approximation algorithm for a string matching problem that is of independent interest.
-
作者：Mohebi, H; Rubinov, A
作者单位：Shahid Bahonar University of Kerman (SBUK); Federation University Australia
摘要：Necessary and sufficient conditions for a local minimum form a well-developed chapter of optimization theory. Determination of such conditions for the global minimum is a challenging problem. Useful conditions are currently known only for a few classes of nonconvex optimization problems. It is important to find different classes of problems for which the required conditions can be obtained. In this paper we examine one of these classes: the minimization of the distance to an arbitrary closed s...
-
作者：Arutyunov, A; Pereira, FL
作者单位：Peoples Friendship University of Russia; Universidade do Porto
摘要：In this article, we derive second-order necessary conditions of optimality for an abstract optimization problem with equality and inequality constraints and constraints in the form of an inclusion into a given closed set. An important feature is that our optimality conditions dispense with any a priori normality assumptions, such as Robinson's constraint qualification, and remain informative even for abnormal points. Moreover, our optimality conditions take into account the second-order effect...
-
作者：Bansal, N; Correa, JR; Kenyon, C; Sviridenko, M
作者单位：International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez; Brown University
摘要：We study the following packing problem: Given a collection of d-dimensional rectangles of specified sizes, pack them into the minimum number of unit cubes. We show that unlike the one-dimensional case, the two-dimensional packing problem cannot have an asymptotic polynomial time approximation scheme (APTAS), unless P = NP. On the positive side, we give an APTAS for the special case of packing d-dimensional cubes into the minimum number of unit cubes. Second, we give a polynomial time algorithm...
-
作者：Van Roy, Benjamin
作者单位：Stanford University
摘要：We consider approximate value iteration with a parameterized approximator in which the state space is partitioned and the optimal cost-to-go function over each partition is approximated by a constant. We establish performance loss bounds for policies derived from approximations associated with fixed points. These bounds identify benefits to using invariant distributions of appropriate policies as projection weights. Such projection weighting relates to what is done by temporal-difference learn...
-
作者：Niño-Mora, J
作者单位：Universidad Carlos III de Madrid
摘要：This paper presents a framework grounded on convex optimization and economics ideas to solve by index policies problems of optimal dynamic allocation of effort to a discrete-state (finite or countable) binary-action (work/rest) semi-Markov restless bandit project, elucidating issues raised by previous work. Its contributions include: (i) the concept of a restless bandit's marginal productivity index (MPI), characterizing optimal policies relative to general cost and work measures; (ii) the cha...
-
作者：Fleischer, Lisa K.; Letchford, Adam N.; Lodi, Andrea
作者单位：Dartmouth College; Lancaster University; University of Bologna
摘要：The comb inequalities are a well-known class of facet-inducing inequalities for the traveling salesman problem, defined in terms of certain vertex sets called the handle and the teeth. We say that a comb inequality is simple if the following holds for each tooth: Either the intersection of the tooth with the handle has cardinality one, or the part of the tooth outside the handle has cardinality one, or both. The simple comb inequalities generalize the classical 2-matching inequalities of Edmon...
-
作者：Lehrer, Ehud; Solan, Eflon
作者单位：Tel Aviv University
摘要：We study the notion of excludability in repeated games with vector payoffs, when one of the players is restricted to strategies with bounded computational capacity. We show that a closed set is excludable by Player 2 when Player 1 is restricted to using only bounded-recall strategies if and only if it does not contain a convex approachable set. We provide partial results when Player 1 is restricted to using strategies that can be implemented by automata.
