检索结果-内蒙古大学图书馆

RANKING ON ARBITRARY GRAPHS: REMATCH VIA continuous linear programming

SIAM JOURNAL ON COMPUTING 2018年第4期47卷 1529-1546页

作者： Chan, T-H Hubert Chen, Fei Wu, Xiaowei Zhao, Zhichao Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

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 linear programming framework. Special care is given to analyze the structural properties of the ranking algorithm in order to derive the linear programming 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.

关键词： oblivious matching problem continuous linear programming ranking algorithm

来源：评论

学校读者我要写书评

暂无评论

continuous-TIME SHORTEST-PATH PROBLEMS AND linear-programming

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1994年第2期32卷 538-552页

作者： PHILPOTT, AB Univ of Auckland Auckland New Zealand

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.

关键词： SHORTEST PATH continuous linear programming EXTREME POINT OPTIMAL SOLUTION DUALITY

来源：评论

学校读者我要写书评

暂无评论

A new algorithm for state-constrained separated continuous linear programs

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1998年第1期37卷 177-210页

作者： Luo, XD Bertsimas, D MIT 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 linear programming 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 continuous linear 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 continuous linear programs contains the separated continuous linear 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.

关键词： continuous linear programming strong duality semi-infinite linear programming nonlinear programming jobshop scheduling problems

来源：评论

学校读者我要写书评

暂无评论

A simplex based algorithm to solve separated continuous linear programs

引用

MATHEMATICAL programming 2008年第1期115卷 151-198页

作者： Weiss, Gideon Univ Haifa Dept Stat IL-31905 Haifa Israel

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... 详细信息

关键词： continuous linear programming simplex method

来源：评论

学校读者我要写书评

暂无评论

The continuous assignment problem and its application to preemptive and non-preemptive scheduling with irregular cost functions

引用

INFORMS JOURNAL ON COMPUTING 2004年第2期16卷 198-208页

作者： Sourd, F Lab Informat Paris 6 F-75252 Paris 05 France

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.

关键词： production-scheduling earliness and tardiness continuous linear programming branch and bound

来源：评论

学校读者我要写书评

暂无评论

An extended algorithm for separated continuous linear programs

引用

MATHEMATICAL programming 2002年第3期93卷 415-451页

作者： Pullan, MC St Johns Coll Cambridge CB2 1TP England

Separated continuous linear programs (SCLP) are a class of continuous linear 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) linear programming 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.

关键词： continuous linear programming linear optimal control simplex-like algorithm

来源：评论

学校读者我要写书评

暂无评论

A duality theory for separated continuous linear programs

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1996年第3期34卷 931-965页

作者： Pullan, MC JUDGE INST MANAGEMENT STUDIES CAMBRIDGE CB2 1RXENGLAND

This paper presents a detailed duality theory for a class of continuous linear programs called separated continuous linear 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.

关键词： duality continuous linear programming linear optimal control

来源：评论

学校读者我要写书评

暂无评论

SYMMETRIC STRONG DUALITY FOR A CLASS OF continuous linear PROGRAMS WITH CONSTANT COEFFICIENTS

引用

SIAM JOURNAL ON OPTIMIZATION 2014年第3期24卷 1102-1121页

作者： Shindin, Evgeny Weiss, Gideon Univ Haifa Dept Stat IL-31905 Har Hakarmel Israel

We consider continuous linear 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).

关键词： continuous linear programming symmetric dual strong duality

来源：评论

学校读者我要写书评

暂无评论

Flows over time in time-varying networks: Optimality conditions and strong duality

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第2期237卷 580-589页

作者： Koch, Ronald Nasrabadi, Ebrahim Tech Univ Berlin Inst Math D-10623 Berlin Germany MIT Ctr Operat Res Cambridge MA 02139 USA

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.

关键词： Flows over time continuous linear programming Optimality conditions Duality

来源：评论

学校读者我要写书评

暂无评论

STRUCTURE OF SOLUTIONS FOR continuous linear PROGRAMS WITH CONSTANT COEFFICIENTS

引用

SIAM JOURNAL ON OPTIMIZATION 2015年第3期25卷 1276-1297页

作者： Shindin, Evgeny Weiss, Gideon Univ Haifa Dept Stat IL-31905 Har Hakarmel Israel

We consider continuous linear 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.

关键词： continuous linear programming symmetric dual strong duality structure of solutions optimization in the space of measures optimal sequence of bases

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：