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

A polynomial path following algorithm for convex programming

APPLIED MATHEMATICS AND COMPUTATION 2008年第2期196卷 866-878页

作者： Fan, Xiaona Yu, Bo Dalian Univ Technol Dept Appl Math Dalian 116024 Peoples R China

In this paper, based on combined homotopy interior point method we propose an interior point algorithm for convex nonlinear programming. The algorithm ensures that the obtained iterative points are interior points of the feasible set in terms of the technique of beta-cone neighborhood. We establish the global convergence of the algorithm. Furthermore, it is shown that the algorithm has O(root nL) iteration complexity. The preliminary numerical experiments indicate that the algorithm is efficient. (C) 2007 Elsevier Inc. All rights reserved.

关键词： convex nonlinear programming combined homotopy path following algorithm global convergence polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximum-cover source-location problems

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2006年第5期E89A卷 1370-1377页

作者： Sugihara, Kenya Ito, Hiro Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan

Given a graph G = (V, E), a set of vertices S subset of V covers v is an element of V if the edge connectivity between S and v is at least a given number k. Vertices in S are called sources. The source location problem is a problem of finding a minimum-size source set covering all vertices of a given graph. This paper presents a new variation of the problem, called maximum-cover source-location problem, which finds a source set S with a given size p, maximizing the sum of the weight of vertices covered by S. It presents an O(np + m + n log n)-time algorithm for k = 2, where n = \V\ and m = \E\. Especially it runs linear time if G is connected. This algorithm uses a subroutine for finding a subtree with the maximum weight among p-leaf trees of a given vertex-weighted tree. For the problem we give a greedy-based linear-time algorithm, which is an extension of the linear-time algorithm for finding a longest path of a given tree presented by E. W. Dijkstra around 1960. Moreover, we show some polynomial solvable cases, e.g., a given graph is a tree or (k - 1)-edge-connected, and NP-hard cases, e.g., a vertex-cost function is given or G is a digraph.

关键词： graph edge-connectivity location problem polynomial-time algorithm NP-hard

来源：评论

学校读者我要写书评

暂无评论

Global probability maximization for a Gaussian bilateral inequality in polynomial time

引用

JOURNAL OF GLOBAL OPTIMIZATION 2017年第4期68卷 879-898页

作者： Minoux, Michel Zorgati, Riadh UPMC LIP6 4 Pl Jussieu F-75252 Paris 05 France EDF Lab Paris Saclay R&D OSIRIS 7 Bd Gaspard Monge F-91120 Palaiseau France

The present paper investigates Gaussian bilateral inequalities in view of solving related probability maximization problems. Since the function f representing the probability of satisfaction of a given Gaussian bilateral inequality is not concave everywhere, we first state and prove a necessary and sufficient condition for negative semi-definiteness of the Hessian. Then, the (nonconvex) problem of globally maximizing f over a given polyhedron in Rn is adressed, and shown to be polynomial-time solvable, thus yielding a new-comer to the (short) list of nonconvex global optimization problems which can be solved exactly in polynomial time. Application to computing upper bounds to the maximum joint probability of satisfaction of a set of m independent Gaussian bilateral inequalities is discussed and computational results are reported.

关键词： Random gaussian inequalities Bilateral chance constraints Global optimization Joint probability maximization polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

WQO is decidable for factorial languages

引用

INFORMATION AND COMPUTATION 2017年 256卷 321-333页

作者： Atminas, Aistis Lozin, Vadim Moshkov, Mikhail London Sch Econ Dept Math Houghton St London WC2A 2AE England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England KAUST CEMSE Div Thuwal 239556900 Saudi Arabia

A language is factorial if it is closed under taking factors, i.e. contiguous subwords. Every factorial language can be described by an antidictionary, i.e. a minimal set of forbidden factors. We show that the problem of deciding whether a factorial language given by a finite antidictionary is well-quasi-ordered under the factor containment relation can be solved in polynomial time. We also discuss possible ways to extend our solution to permutations and graphs. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Well-quasi-ordering Factorial language polynomial-time algorithm Induced subgraph Permutation

来源：评论

学校读者我要写书评

暂无评论

(Strong) conflict-free connectivity: algorithm and complexity

引用

THEORETICAL COMPUTER SCIENCE 2020年 804卷 72-80页

作者： Ji, Meng Li, Xueliang Zhu, Xiaoyu Nankai Univ Ctr Combinator Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China

Let G be an(a) edge(vertex)-colored graph. A path P of G is called a conflict-free path if there is a color that is used on exactly one of the edges(vertices) of P. The graph G is called conflict-free (vertex-)connected if any two distinct vertices of G are connected by a conflict-free path, whereas the graph G is called strongly conflict-free connected if any two distinct vertices u, v of G are connected by a conflict-free path of length of a shortest path between u and v in G. For a connected graph G, the (strong)conflict-free connection number of G, denoted by (scfc(G)) cf c(G), is defined as the smallest number of colors that are required to make G (strongly) conflict-free connected. In this paper, we first investigate the question: Given a connected graph G and a coloring c : E(or V) ->{1, 2, ..., k} (k >= 1) of G, determine whether or not G is, respectively, conflict-free connected, conflict-free vertexconnected, strongly conflict-free connected under the coloring c. We solve this question by providing polynomial-time algorithms. We then show that the problem of deciding whether scfc(G) <= k (k >= 2) for a given graph G is NP-complete. Moreover, we prove that it is NP-complete to decide whether there is a k-edge-coloring (k >= 2) of G such that all pairs (u, v) is an element of P (P subset of V x V) are strongly conflict-free connected. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Conflict-free connection polynomial-time algorithm Strong conflict-free connection Complexity

来源：评论

学校读者我要写书评

暂无评论

Differentiating-total domination: Approximation and hardness results

引用

THEORETICAL COMPUTER SCIENCE 2021年 876卷 45-58页

作者： Panda, B. S. Goyal, Pooja Pradhan, D. Indian Inst Technol Dept Math Delhi India Indian Inst Technol ISM Dept Math & Comp Dhanbad Bihar India

A total dominating set of a graph G = (V, E) is a subset D of V such that every vertex in V is adjacent to at least one vertex of the set D. A total dominating set D of G is a differentiating-total dominating set of G if for every pair of distinct vertices u, v is an element of V, N-G[u] boolean AND D not equal N-G[v] boolean AND D. Given a graph G, MINIMUM DIFFERENTIATING-TOTAL DOMINATION is to find a differentiating-total dominating set of minimum cardinality of G and DECIDE DIFFERENTIATING-TOTAL DOMINATION is the decision version of MINIMUM DIFFERENTIATING-TOTAL DOMINATION. In this paper, we initiate the algorithmic study of MINIMUM DIFFERENTIATING-TOTAL DOMINATION. We show that DECIDE DIFFERENTIATING-TOTAL DOMINATION is NP-complete for chordal graphs, chordal bipartite graphs, star-convex bipartite graphs, and planar graphs. On the positive side, we propose an O (log A) factor approximation algorithm for MINIMUM DIFFERENTIATING-TOTAL DOMINATION for any graph G with maximum degree delta. We match the above upper bound by showing that for general graphs as well as for bipartite graphs MINIMUM DIFFERENTIATING-TOTAL DOMINATION cannot be approximated within a factor of (1/2 - is an element of)ln vertical bar V vertical bar for any is an element of > 0 unless P= NP. Finally, we show that MINIMUM DIFFERENTIATING-TOTAL DOMINATION is APX-complete for bounded degree bipartite graphs. (C) 2021 Published by Elsevier B.V.

关键词： Domination Total domination Differentiating-total domination polynomial-time algorithm NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

Task scheduling with progress control

引用

IISE TRANSACTIONS 2018年第1期50卷 54-61页

作者： Li, Chung-Lun Zhong, Weiya Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Shanghai Univ Sch Management Dept Business Adm Shanghai Peoples R China

Tasks with long durations often face the requirement of having to periodically report their progress to process controllers. Under this requirement, working teams that simultaneously process multiple tasks need to schedule their work carefully in order to demonstrate satisfactory progress on each unfinished task. We present a single-machine scheduling model that reflects this requirement. Our model has multiple milestones at which the tasks are penalized if their progress is below a satisfactory level. We develop polynomial solution methods for the general case with convex nonlinear penalty functions and for the special case with linear penalty functions. Extensions of our model are also discussed.

关键词： Scheduling multi-tasking polynomial-time algorithm progress milestones

来源：评论

学校读者我要写书评

暂无评论

Improved complexity results on solving real-number linear feasibility problems

引用

MATHEMATICAL PROGRAMMING 2006年第2期106卷 339-363页

作者： Ye, YY Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A is an element of R-m x n, the right-hand-side vector b is an element of R-m and the objective coefficient vector c is an element of R-n are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x >= 0, can be solved in in O(n(2.5)c(A)) interior-point method iterations. Here 0 is the vector of all zeros and c(A) is the condition measure of matrix A defined in [25]. This complexity iteration bound is reduced by a factor n from that for general LP(A, b, c) in [ 25]. We also prove that the iteration bound will be further reduced to O(n(1.5)c(A)) for LP(A, 0, 0), i.e., for the homogeneous linear feasibility problem. These results are surprising since the classical view has been that linear feasibility would be as hard as linear programming.

关键词： polynomial-time algorithm INTERIOR-POINT algorithmS PATH VARIANT variants Complexity Chpher(0) Zero Element Cloning Vectors Lipoprotein(a) Linear linear programming iterative methods polynomial time

来源：评论

学校读者我要写书评

暂无评论

PACKING AND COVERING WITH INTEGRAL FEASIBLE FLOWS IN INTEGRAL SUPPLY-DEMAND NETWORKS

引用

MATHEMATICAL PROGRAMMING 1987年第3期39卷 231-239页

作者： BIXBY, RE MARCOTTE, OMC TROTTER, LE UNIV QUEBEC DEPT MATH & INFORMATMONTREAL H3C 3P8QUEBECCANADA CORNELL UNIV SCH OREIEITHACANY 14853

polynomial-time algorithms are presented for solving combinatorial packing and covering problems defined from the integral feasible flows in an integral supply-demand network. These algorithms are also shown to apply to packing and covering problems defined by the minimal integral solutions to general totally unimodular systems. Analogous problems arising from matroid bases are also discussed and it is demonstrated that a means for solving such problems is provided by recent work of Cunningham.

关键词： Network flows covering and packing polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Strong triadic closure in cographs and graphs of low maximum degree

引用

THEORETICAL COMPUTER SCIENCE 2018年 740卷 76-84页

作者： Konstantinidis, Athanasios L. Nikolopoulos, Stavros D. Papadopoulos, Charis Univ Ioannina Dept Math Ioannina Greece Univ Ioannina Dept Comp Sci & Engn Ioannina Greece

The MAxSTC problem is an assignment of the edges with two types of labels, namely, strong and weak, that maximizes the number of strong edges such that any two vertices that have a common neighbor with a strong edge are adjacent. The CLUSTER DELETION problem seeks for the minimum number of edge removals of a given graph such that the remaining graph is a disjoint union of cliques. Both problems are known to be NP-hard and an optimal solution for the CLUSTER DELETION problem provides a feasible solution for the MAxSTC problem, however not necessarily an optimal one. In this work we conduct the first systematic study that reveals graph families for which the optimal solutions for MAxSTC and CLUSTER DELETION coincide. We first show that MAxSTC coincides with CLUSTER DELETION on cographs and, thus, MAxSTC is solvable in polynomial time on cographs. As a side result, we give an interesting computational characterization of the maximum independent set on the cartesian product of two cographs. Furthermore, we address the influence of the low degree bounds to the complexity of the MAxSTC problem. We show that this problem is polynomial-time solvable on graphs of maximum degree three, whereas MAxSTC becomes NP-complete on graphs of maximum degree four. The proof of the latter result implies that there is no subexponential-time algorithm for MAxSTC unless the Exponential-time Hypothesis fails. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Strong triadic closure Cluster deletion Cographs Bounded degree graphs NP-completeness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：