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

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

来源：评论

学校读者我要写书评

暂无评论

A simplex-type algorithm for continuous linear programs with constant coefficients

引用

MATHEMATICAL programming 2020年第1-2期180卷 157-201页

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

We consider continuous linear programs over a continuous finite time horizon T, with a constant coefficient matrix, linear right hand side functions and linear cost coefficient functions. Specifically, 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 previous papers we formulated a symmetric dual and have shown strong duality. We also have presented a detailed description of optimal solutions and have defined a combinatorial analogue to basic solutions of standard LP. In this paper we present an algorithm which solves this class of problems in a finite bounded number of steps, using an analogue of the simplex method, in the space of measures.

关键词： Optimal control continuous linear programming Simplex-type algorithm

来源：评论

学校读者我要写书评

暂无评论

A Multicriteria Economic Analysis Model for Urban Forestry Projects 3rd

A Multicriteria Economic Analysis Model for Urban Forestry P...

引用

3rd International Symposium on New Metropolitan Perspectives - Local Knowledge and Innovation Dynamics Towards Territory Attractiveness Through the Implementation of Horizon/E2020/Agenda2030

作者： Guarini, Maria Rosaria Nestico, Antonio Morano, Pierluigi Sica, Francesco Sapienza Univ Rome I-00185 Rome Italy Univ Salerno I-84084 Fisciano Italy Polytech Univ Bari I-70126 Bari Italy

ISBN: (纸本)9783319920993;9783319920986

The urban green areas represent a strategic resource for the contemporary city sustainable development. In addition to aesthetic and recreational functions, their presence contributes to increase the environmental quality level by improving the microclimate, preserving the biodiversity and promoting the territory economic growth. However, the interventions execution designed to provide the built areas of the so-called urban forests is rarely indicated as a priority action in the urban spaces planning because often a different allocation of available resources is preferred. In this work, starting from the definition of a indicators set useful for expressing the not only financial, but also social, cultural and environmental components of value of the projects for urban forestry, the aim is to build a multi-criteria economic analysis protocol purposeful at predicting the correct funds distribution between initiatives for realization of urban forests at a district scale. The characterization of the model is carried out through the logical-mathematical tools of the Operational Research developed according to continuous linear programming principles.

关键词： Urban forestry Economic evaluation Sustainable development Multi-criteria decision analysis continuous linear programming

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Ranking on Arbitrary Graphs: Rematch via continuous LP with Monotone and Boundary Condition Constraints 14

Ranking on Arbitrary Graphs: Rematch via Continuous LP with ...

引用

Annual ACM-SIAM Symposium on Discrete Algorithms

作者： T. H. Hubert Chan Fei Chen Xiaowei Wu Zhichao Zhao The University of Hong Kong

ISBN: (纸本)9781611973389

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 performance ratio 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 proved that the Modified Randomized Greedy algorithm achieves performance ratio 0.5+ε (where ε = 1/400000 ) on arbitrary graphs in the mid-nineties, 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. In this paper, we revisit the Ranking algorithm using the LP framework. Special care is given to analyze the structural properties of the Ranking algorithm in order to derive the LP constraints, of which one known as the boundary constraint requires totally new analysis and is crucial to the success of our LP. We use continuous LP 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 LP. Our work achieves the currently best the oretical performance ratio of 2(5-7~(1/2))/9≈0:523 on arbitrary graphs. Moreover, experiments suggest that Ranking cannot perform better than 0:724 in general.

关键词： continuous linear programming

来源：评论

学校读者我要写书评

暂无评论

POLYNOMIAL APPROXIMATIONS FOR continuous linear PROGRAMS

引用

SIAM JOURNAL ON OPTIMIZATION 2012年第2期22卷 628-648页

作者： Bampou, Dimitra Kuhn, Daniel Univ London Imperial Coll Sci Technol & Med Dept Comp London SW7 2BZ England

continuous linear programs have attracted considerable interest due to their potential for modeling manufacturing, scheduling, and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude time discretization remains the method of choice for solving general (nonseparated) problem instances. In this paper we propose a more generic approximation scheme for nonseparated continuous linear programs, where we approximate the functional decision variables (policies) by polynomial and piecewise polynomial decision rules. This restriction results in an upper bound on the original problem, which can be computed efficiently by solving a tractable semidefinite program. To estimate the approximation error, we also compute a lower bound by solving a dual continuous linear program in (piecewise) polynomial decision rules. We establish the convergence of the primal and dual approximations under Slater-type constraint qualifications. We also highlight the potential of our method for optimizing large-scale multiclass queueing systems and dynamic Leontief models.

关键词： continuous linear programming polynomial decision rules conic programming

来源：评论

学校读者我要写书评

暂无评论

On solving continuous-time dynamic network flows

引用

JOURNAL OF GLOBAL OPTIMIZATION 2012年第3期53卷 497-524页

作者： Hashemi, S. Mehdi Nasrabadi, Ebrahim Tech Univ Berlin Inst Math D-10623 Berlin Germany Amirkabir Univ Technol Dept Comp Sci Tehran Iran

Temporal dynamics is a crucial feature of network flow problems occurring in many practical applications. Important characteristics of real-world networks such as arc capacities, transit times, transit and storage costs, demands and supplies etc. are subject to fluctuations over time. Consequently, also flow on arcs can change over time which leads to so-called dynamic network flows. While time is a continuous entity by nature, discrete-time models are often used for modeling dynamic network flows as the resulting problems are in general much easier to handle computationally. In this paper, we study a general class of dynamic network flow problems in the continuous-time model, where the input functions are assumed to be piecewise linear or piecewise constant. We give two discrete approximations of the problem by dividing the considered time range into intervals where all parameters are constant or linear. We then present two algorithms that compute, or at least converge to optimum solutions. Finally, we give an empirical analysis of the performance of both algorithms.

关键词： Dynamic network flows continuous linear programming Discretization Duality

来源：评论

学校读者我要写书评

暂无评论

Solution Algorithms for a Class of continuous linear Programs with Fuzzy Valued Objective Functions

引用

FUZZY INFORMATION AND ENGINEERING 2010年第1期2卷 5-26页

作者： Nasrabadi, Mohammad Mehdi Yaghoobi, Mohammad Ali Mashinchi, Mashaallah Shahid Bahonar Univ Kerman Fac Math & Comp Dept Math Kerman Iran Shahid Bahonar Univ Kerman Fac Math & Comp Dept Stat Kerman Iran

This paper discusses a class of continuous linear programs with fuzzy valued objective functions. A member of this class is called a fuzzy separated continuous linear program (FSCLP). Such problems have applications in a number of domains, including, production and inventory systems, communication networks, and pipeline systems for transportation. The discretization approach is used to construct two ordinary fuzzy linear programming problems, which give a lower and an upper bound on the optimal value of FSCLP. It is then shown how to construct an improved feasible solution for FSCLP starting from a nonoptimal one. This leads to the development of a class of algorithms based on a sequence of discrete approximations to FSCLP. Numerical examples in the context of continuous-time networks are presented to show the applicability of the proposed method.

关键词： continuous linear programming Fuzzy linear programming Duality Discretization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：