Motivated by online advertisement and exchange settings, greedy randomized algorithms for the maximum matching problem have been studied, in which the algorithm makes (random) decisions that are essentially oblivious ...
详细信息
Motivated by online advertisement and exchange settings, greedy randomized algorithms for the maximum matching problem have been studied, in which the algorithm makes (random) decisions that are essentially oblivious to the input graph. Any greedy algorithm can achieve a performance ratio of 0.5, which is the expected number of matched nodes to the number of nodes in a maximum matching. Since Aronson, Dyer, Frieze, and Suen [Random Structures Algorithm, 6 (1991), pp. 29-46] proved that the modified randomized greedy algorithm achieves a performance ratio of 0:5 + epsilon (where epsilon = 1/400000) on arbitrary graphs in the midnineties, no further attempts in the literature have been made to improve this theoretical ratio for arbitrary graphs until two papers were published in FOCS 2012 [G. Goel and P. Tripathi, IEEE Computer Society, Los Alamitos, CA, 2012, pp. 718-727;M. Poloczek and M. Szegedy, IEEE Computer Society, Los Alamitos, CA, 2012, pp. 708-717]. In this paper, we revisit the ranking algorithm using the linearprogramming framework. Special care is given to analyze the structural properties of the ranking algorithm in order to derive the linearprogramming constraints, of which one known as the boundary constraint requires totally new analysis and is crucial to the success of our linear program (LP). We use continuous linear programming relaxation to analyze the limiting behavior as the finite LP grows. Of particular interest are new duality and complementary slackness characterizations that can handle the monotone and the boundary constraints in continuous linear programming. Improving previous work, this paper achieves a theoretical performance ratio of 2(5-root 7)/9 approximate to 0.523 on arbitrary graphs.
Shortest path problems are considered for a graph in which edge distances can vary with time, each edge has a transit time, and parking (with a corresponding penalty) is allowed at the vertices. The problem is formula...
详细信息
Shortest path problems are considered for a graph in which edge distances can vary with time, each edge has a transit time, and parking (with a corresponding penalty) is allowed at the vertices. The problem is formulated an a continuous-time linear program, and a dual problem is derived for which the absence of a duality gap is proved. The existence of an extreme-point solution to the continuous-time linear program is also demonstrated, and a correspondence is derived extreme points and continuous-time shortest paths. Strong duality is then derived in the case where the edge distances satisfy a Lipschitz condition.
作者:
Luo, XDBertsimas, DMIT
Alfred P Sloan Sch Management Cambridge MA 02139 USA MIT
Ctr Operat Res Cambridge MA 02139 USA
During the last few decades, significant progress has been made in solving large-scale finite-dimensional and semi-infinite linearprogramming problems. In contrast, little progress has been made in solving linear pro...
详细信息
During the last few decades, significant progress has been made in solving large-scale finite-dimensional and semi-infinite linearprogramming problems. In contrast, little progress has been made in solving linear programs in infinite-dimensional spaces despite their importance as models in manufacturing and communication systems. Inspired by the research on separated continuouslinear programs, we propose a new class of continuous linear programming problems that has a variety of important applications in communications, manufacturing, and urban traffic control. This class of continuouslinear programs contains the separated continuouslinear programs as a subclass. Using ideas from quadratic programming, we propose an efficient algorithm for solving large-scale problems in this new class under mild assumptions on the form of the problem data. We prove algorithmically the absence of a duality gap for this class of problems without any boundedness assumptions on the solution set. We show this class of problems admits piecewise constant optimal control when the optimal solution exists. We give conditions for the existence of an optimal solution. We also report computational results which illustrate that the new algorithm is effective in solving large-scale realistic problems (with several hundred continuous variables) arising in manufacturing systems.
We consider the separated continuous linear programming problem with linear data. We characterize the form of its optimal solution, and present an algorithm which solves it in a finite number of steps, using an analog...
详细信息
We consider the separated continuous linear programming problem with linear data. We characterize the form of its optimal solution, and present an algorithm which solves it in a finite number of steps, using an analog of the simplex method, in the space of bounded measurable functions.
This paper focuses on the continuous assignment problem with the eventual aim to solve scheduling problems with irregular cost functions. It consists of partitioning a region of R-d into subregions of prescribed volum...
详细信息
This paper focuses on the continuous assignment problem with the eventual aim to solve scheduling problems with irregular cost functions. It consists of partitioning a region of R-d into subregions of prescribed volumes so that the total cost is minimized. The dual problem of the continuous assignment problem is an unconstrained maximization of a non-smooth concave function. The preemptive variant of the scheduling problem with irregular cost functions corresponds to the one-dimensional continuous assignment problem and a lower bound for the non-preemptive variant can be derived. It is computationally tested in a branch-and-bound algorithm.
Separated continuouslinear programs (SCLP) are a class of continuouslinear programs which, among other things, can serve as a useful model for dynamic network problems where storage is permitted at the nodes. Recent...
详细信息
Separated continuouslinear programs (SCLP) are a class of continuouslinear programs which, among other things, can serve as a useful model for dynamic network problems where storage is permitted at the nodes. Recent work on SCLP has produced a detailed duality theory, conditions under which an optimal solution exists with a finite number of breakpoints, a purification algorithm, as well as a convergent algorithm for solving SCLP under certain assumptions on the problem data. This paper combines much of this work to develop a possible approach for solving a wider range of SCLP problems, namely those with fairly general costs. The techniques required to implement the algorithm are no more than standard (finite-dimensional) linearprogramming and line searching, and the resulting algorithm is simplex-like in nature. We conclude the paper with the numerical results obtained by using a simple implementation of the algorithm to solve a small problem.
This paper presents a detailed duality theory for a class of continuouslinear programs called separated continuouslinear programs (SCLP), based on a particular dual problem SCLP*. Using weak duality, a notion of com...
详细信息
This paper presents a detailed duality theory for a class of continuouslinear programs called separated continuouslinear programs (SCLP), based on a particular dual problem SCLP*. Using weak duality, a notion of complementary slackness is introduced, and several sufficient conditions for optimality of SCLP are derived along with the existence of complementary slack variables for basic feasible solutions for SCLP. Following this, a fairly general condition for the absence of a duality gap between SCLP and SCLP* is given, as are several conditions for the existence of an optimal solution for SCLP*. Finally, using all these ingredients, a strong duality result between SCLP and SCLP* is proven when the problem data are piecewise analytic. A simple counterexample is presented to show that strong duality may not follow if the assumptions of piecewise analyticity do not hold.
We consider continuouslinear programs over a continuous finite time horizon T, with linear cost coefficient functions and linear right-hand side functions and a constant coefficient matrix, where we search for optima...
详细信息
We consider continuouslinear programs over a continuous finite time horizon T, with linear cost coefficient functions and linear right-hand side functions and a constant coefficient matrix, where we search for optimal solutions in the space of measures or of functions of bounded variation. These models generalize the separated continuous linear programming models and their various duals, as formulated in the past by Anderson, by Pullan, and by Weiss. We present simple necessary and sufficient conditions for feasibility. We formulate a symmetric dual and investigate strong duality by considering discrete time approximations. We prove that under a Slater type condition there is no duality gap and there exist optimal solutions which have impulse controls at 0 and T and have piecewise constant densities in (0, T). Moreover, we show that under nondegeneracy assumptions all optimal solutions are of this form, and are uniquely determined over (0, T).
There has been much research on network flows over time due to their important role in real world applications. This has led to many results, but the more challenging continuous time model still lacks some of the key ...
详细信息
There has been much research on network flows over time due to their important role in real world applications. This has led to many results, but the more challenging continuous time model still lacks some of the key concepts and techniques that are the cornerstones of static network flows. The aim of this paper is to advance the state of the art for dynamic network flows by developing the continuous time analogues of the theory for static network flows. Specifically, we make use of ideas from the static case to establish a reduced cost optimality condition, a negative cycle optimality condition, and a strong duality result for a very general class of network flows over time. (C) 2014 Elsevier B.V. All rights reserved.
We consider continuouslinear programs over a continuous finite time horizon T, with linear cost coefficient functions, linear right-hand side functions, and a constant coefficient matrix, as well as their symmetric d...
详细信息
We consider continuouslinear programs over a continuous finite time horizon T, with linear cost coefficient functions, linear right-hand side functions, and a constant coefficient matrix, as well as their symmetric dual. We search for optimal solutions in the space of measures or of functions of bounded variation. These models generalize the separated continuous linear programming models and their various duals, as formulated in the past by Anderson, by Pullan, and by Weiss. In a recent paper, we have shown that under a Slater-type condition, these problems possess optimal strongly dual solutions. In this paper, we give a detailed description of optimal solutions and define a combinatorial analogue to basic solutions of standard LP. We also show that feasibility implies existence of strongly dual optimal solutions without requiring the Slater condition. We present several examples to illustrate the richness and complexity of these solutions.
暂无评论