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

IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT)

作者： Wang, Pei-Zhuang Guo, Si-cong Lui, Ho-Chung He, Jing Kong, Qi-wei Shi, Yong Liaoning Tech Univ Fuxin Liaoning Peoples R China Nanjing Univ Finance & Econ Inst Informat Engn Nanjing Peoples R China Chinese Acad Sci Res Ctr Fictitious Econ & Data Sci Beijing Peoples R China

ISBN: (纸本)9781450391153

The existence of strongly polynomial-time algorithm for linear programming is a cross century international mathematical problem, whose breakthrough will solve a major theoretical crisis for the development of artificial intelligence. In order to make it happen, this paper proposes three solving techniques based on the conecutting theory: 1. The selection of cutter: principles highest vs. deepest;2. The algorithm of column elimination, which is more convenient and effective than the Ye-column elimination theorem;3. A step-down algorithm for a feasible point horizontally shifts to the center and then falls down to the bottom of the dual feasible region D. There will be a nice work combining three techniques, the tri-skill is variant Simplex algorithm to be expected to help readers building the strong polynomial algorithms. Besides, a variable weight optimization method is proposed in the paper, which opens a new window to bring the linear programming into uncomplicated calculation.

关键词： Linear programming strongly polynomial-time algorithm Conecutting Column elimination algorithm Factor space

来源：评论

学校读者我要写书评

暂无评论

A strongly polynomial time algorithm for the maximum supply rate problem on trees

引用

THEORETICAL COMPUTER SCIENCE 2020年 806卷 323-331页

作者： Takayama, Koki Kobayashi, Yusuke Univ Tsukuba Tsukuba Ibaraki 3058573 Japan Kyoto Univ Kyoto 6068502 Japan

Suppose that we are given a graph whose each vertex is either a supply vertex or a demand vertex and is assigned a nonnegative integer supply or demand value. We consider partitioning G into connected components by removing edges from G so that each connected component has exactly one supply vertex and there exists a flow in each connected component satisfying the supply/demand constraints. The problem that determines the existence of such a partition is called the partition problem. Ito et al. (2005) showed that the partition problem is NP-complete in general and it can be solved in linear time if the given graph is a tree. When the graph does not have such a partition, we scale the demand values uniformly by scale factor r so that the obtained graph has a desired partition. The maximum supply rate problem is the problem that finds the maximum value of such r. Whereas the maximum supply rate problem is NP-hard in general in the same way as the partition problem, Morishita and Nishizeki (2015) gave a weakly polynomial-time algorithm for the problem on trees. In this paper, we give a first strongly polynomial-time algorithm for the maximum supply rate problem on trees. Our algorithm is based on the dynamic programming technique, in which we compute "surplus" and "deficit" of the supply in subproblems from leaves to the root. We use piecewise linear functions of r to represent them, and one of our important contributions is to bound the size of the representation of each function. (C) 2019 Elsevier B.V. All rights reserved.

关键词： strongly polynomial-time algorithm Dynamic programming Maximum supply rate problem

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of Binary polynomial Optimization Over Acyclic Hypergraphs

引用

algorithmICA 2023年第8期85卷 2189-2213页

作者： Del Pia, Alberto Di Gregorio, Silvia Univ Wisconsin Madison Dept Ind & Syst Engn 1513 Univ Ave Madison WI 53706 USA Univ Wisconsin Madison Wisconsin Inst Discovery 330 North Orchard St Madison WI 53715 USA Tech Univ Dresden Fac Comp Sci Nothnitzer Str 46 D-01187 Dresden Germany

In this work, we advance the understanding of the fundamental limits of computation for binary polynomial optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novelclass of BPO that can be solved efficiently both from a theoretical and computational perspective. In fact, we give a strongly polynomial-time algorithm for instances whosec orresponding hypergraph is beta-acyclic. We note that the beta-acyclicity assumption isnatural in several applications including relational database schemes and the liftedmulticut problem on trees. Due to the novelty of our proving technique, we obtainan algorithm which is interesting also from a practical viewpoint. This is becauseour algorithm is very simple to implement and the running time is a polynomial ofvery low degree in the number of nodes and edges of the hypergraph. Our result completely settles the computational complexity of BPO over acyclic hypergraphs,since the problem is NP-hard on alpha-acyclic instances. Our algorithm can also be appliedto any general BPO problem that contains beta-cycles. For these problems, the algorithmreturns a smaller instance together with a rule to extend any optimal solution of thesmaller instance to an optimal solution of the original instance.

关键词： Binary polynomial optimization strongly polynomial-time algorithm Acyclic hypergraphs Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

Partial inverse min-max spanning tree problem under the weighted bottleneck hamming distance

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第4期46卷 27-27页

作者： Dong, Qingzhen Li, Xianyue Yang, Yu Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China

Min-max spanning tree problem is a classical problem in combinatorial optimization. Its purpose is to find a spanning tree to minimize its maximum edge in a given edge weighted graph. Given a connected graph G, an edge weight vector w and a forest F, the partial inverse min-max spanning tree problem (PIMMST) is to find a new weighted vector w*, so that F can be extended into a min-max spanning tree with respect to w* and the gap between w and w* is minimized. In this paper, we research PIMMST under the weighted bottleneck Hamming distance. Firstly, we study PIMMST with value of optimal tree restriction, a variant of PIMMST, and show that this problem can be solved in strongly polynomial time. Then, by characterizing the properties of the value of optimal tree, we present first algorithm for PIMMST under the weighted bottleneck Hamming distance with running time O(vertical bar E vertical bar(2) log vertical bar E vertical bar), where E is the edge set of G. Finally, by giving a necessary and sufficient condition to determine the feasible solution of this problem, we present a better algorithm for this problem with running time O(vertical bar E vertical bar log vertical bar E vertical bar). Moreover, we show that these algorithms can be generalized to solve these problems with capacitated constraint.

关键词： Partial inverse problem Min-max spanning tree Weighted bottleneck hamming distance strongly polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

An incentive compatible, efficient market for air traffic flow management

引用

THEORETICAL COMPUTER SCIENCE 2020年 818卷 41-50页

作者： Mehta, Ruta Vazirani, Vijay V. Univ Illinois Dept Comp Sci Champaign IL 61820 USA Univ Calif Irvine Irvine CA 92717 USA

We present a market-based approach to the Air Traffic Flow Management (ATFM) problem. The goods in our market are delays and buyers are airline companies;the latter pay money to the Federal Aviation Administration (FAA) to buy away the desired amount of delay on a per flight basis. We give a notion of equilibrium for this market and an LP whose every optimal solution gives an equilibrium allocation of flights to landing slots as well as equilibrium prices for the landing slots. Via a reduction to matching, we show that this equilibrium can be computed combinatorially in strongly polynomial time. Moreover, there is a special set of equilibrium prices, which can be computed easily, that is identical to the VCG solution, and therefore the market is incentive compatible (truthful) in dominant strategy. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Market equilibrium Matching market strongly polynomial-time algorithm Incentive compatible VCG

来源：评论

学校读者我要写书评

暂无评论

An incentive compatible, efficient market for air traffic flow management 23rd

An incentive compatible, efficient market for air traffic fl...

引用

23rd International Computing and Combinatorics Conference (COCOON)

作者： Mehta, Ruta Vazirani, Vijay V. Univ Illinois Dept Comp Sci Champaign IL 61820 USA Univ Calif Irvine Irvine CA 92717 USA

ISBN: (纸本)9783319623887

关键词： Market equilibrium Matching market strongly polynomial-time algorithm Incentive compatible VCG

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for packing cuts and (2,3)-metrics in a planar graph with three holes

引用

DISCRETE OPTIMIZATION 2019年 33卷 118-139页

作者： Karzanov, Alexander, V RAS Cent Inst Econ & Math 47 Nakhimovskii Prospect Moscow 117418 Russia

We consider a planar graph G in which the edges have nonnegative integer lengths such that the length of every cycle of G is even, and three faces are distinguished, called holes in G. It is known that there exists a packing of cuts and (2,3)-metrics with nonnegative integer weights in G which realizes the distances within each hole. We develop a purely combinatorial strongly polynomial-time algorithm to find such a packing. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Packing problem strongly polynomial-time algorithm Planar graph Cut (2,3)-metric Shortest path

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：