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

14th International Conference Integer Programming and Combinatorial Optimization

作者： Hemmecke, Raymond Koeppe, Matthias Weismantel, Robert Tech Univ Munich D-8000 Munich Germany Univ Calif Davis CA USA ETH Zurich Switzerland

ISBN: (纸本)9783642130359

In this paper we generalize N-fold integer programs and two-stage integer programs with AT scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks but variable N, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable N and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.

关键词： N-fold integer programs Graver basis augmentation algorithm polynomial-time algorithm stochastic multi-commodity flow stochastic integer programming

来源：评论

学校读者我要写书评

暂无评论

A near-linear time algorithm and a min-cost flow approach for determining the optimal landing times of a fixed sequence of planes

引用

ANNALS OF OPERATIONS RESEARCH 2025年第1期344卷 479-498页

作者： Cao, Bin Xu, Chao Jinan Univ Sch Management Guangzhou 510632 Peoples R China Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China

The aircraft landing problem (ALP) is an important issue of assigning an airport's runways to the arrival aircrafts as well as to schedule the landing time of these aircrafts in practice. A large number of the extant studies have tried to address such a practical problem with using various algorithms for one or more runways. For a static single-runway of the ALP, this paper proposes a new approach to develop an alternative powerful algorithm. For a given sequence of planes, we develop a faster algorithm for solving the ALP with the running time O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n \log n)$$\end{document}, where n is the number of aircrafts in the schedule. Alternatively, we reduce the proposed problem of minimizing the total cost by determining the landing times for a given landing sequence into a min-cost flow problem. We conduct a set of experimental studies to compare the performance of our near-linear time algorithm to the quadratic time algorithm whose time complexity is O(n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>2)$$\end{document}, for computing the optimal landing times. The computational results show that the proposed heuristic based on our algorithm could be much faster than both such quadratic time algorithm and the one using linear programming.

关键词： Aircraft landing problem static single-runway system Scheduling Min-cost flow polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Graph Bipartization and Via Minimization for Intersection Graphs

引用

JOURNAL OF INTERCONNECTION NETWORKS 2025年第2期25卷

作者： Lin, Lan Lin, Yixun Tongji Univ Sch Elect & Informat Engn Shanghai 200092 Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

The graph bipartization problem, arising from via minimization in VLSI design and related areas, consists in finding a vertex subset S of graph G such that the induced subgraph G[S] is bipartite and |S| is maximized. The problem has been proved to be NP-hard even for planar graphs and cubic graphs. On the other hand, the study of polynomial-time algorithms for typical graph classes is significant in both theoretical and applied aspects. This paper focuses on several intersection graph classes, such as line graphs, circular-arc graphs, and directed path graphs. For the line graphs, we show the NP-hardness results in general and present the polynomial-time algorithms for special cases. For circular-arc graphs and directed path graphs, we propose algorithms that improve on the previously known ones.

关键词： Bipartite induced subgraph odd-cycle transversal via minimization NP-hardness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for Phylogenetic Inference Problems Involving Duplication and Reticulation

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2020年第1期17卷 14-26页

作者： van Iersel, Leo Janssen, Remie Jones, Mark Murakami, Yukihiro Zeh, Norbert Delft Univ Technol Delft Inst Appl Math Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands Dalhousie Univ Fac Comp Sci 6050 Univ Ave Halifax NS B3H 1W5 Canada

A common problem in phylogenetics is to try to infer a species phylogeny from gene trees. We consider different variants of this problem. The first variant, called Unrestricted Minimal Episodes Inference, aims at inferring a species tree based on a model with speciation and duplication where duplications are clustered in duplication episodes. The goal is to minimize the number of such episodes. The second variant, Parental Hybridization, aims at inferring a species network based on a model with speciation and reticulation. The goal is to minimize the number of reticulation events. It is a variant of the well-studied Hybridization Number problem with a more generous view on which gene trees are consistent with a given species network. We show that these seemingly different problems are in fact closely related and can, surprisingly, both be solved in polynomial time, using a structure we call "beaded trees". However, we also show that methods based on these problems have to be used with care because the optimal species phylogenies always have a restricted form. To mitigate this problem, we introduce a new variant of Unrestricted Minimal Episodes Inference that minimizes the duplication episode depth. We prove that this new variant of the problem can also be solved in polynomial time.

关键词： Phylogenetics duplication MINIMUM EPISODES problem HYBRIDIZATION NUMBER problem gene trees inference polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for Checking Some Properties of Boolean Functions Given by polynomials

引用

THEORY OF COMPUTING SYSTEMS 2016年第3期58卷 383-391页

作者： Selezneva, Svetlana N. Bukhman, Anton V. Moscow MV Lomonosov State Univ Fac Computat Math & Cybernet Moscow Russia

In this paper, we show that checking some properties of Boolean functions which are given by the lists of monomials in their polynomial representations can be implemented in polynomial time. Multi-linear polynomials over GF(2) are often a convenient way to represent Boolean functions. There is a single polynomial for each Boolean function, and the length of the polynomial (i.e. the number of its monomials) which represents a function of n variables can be far less than 2(n). Therefore, in some cases, polynomials are a compressed description of Boolean functions. Besides, polynomial representations of Boolean functions have applications in circuit lower bounds, computational learning, error-correcting codes, cryptography. We construct polynomial-time algorithms for checking some properties of Boolean functions which are given by the lists of monomials in their polynomial representations. The considered properties are self-anti-duality (evenness), self-duality, periodicity, 1-invariance (Mobius transform invariance, coincidence). Note that checking each of these properties directly by definition gives, in the general case, only exponential-time algorithms. The approach to construct our algorithms is the following. Firstly, we prove that if a Boolean function has a certain property then its polynomial has a special structure. And secondly, we check the property by its characterization, cutting negative cases by proven facts. More precisely, we analyze an exponential time algorithm and prove that if the number of steps of the algorithm exceeds a bound, which is polynomial in the input size, and may be computed in advance, then the input will be necessarily rejected.

关键词： Boolean function polynomial representation List of monomials Computational complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for SUBGRAPH ISOMORPHISM in small graph classes of perfect graphs

引用

DISCRETE APPLIED MATHEMATICS 2016年 199卷 37-45页

作者： Konagaya, Matsuo Otachi, Yota Uehara, Ryuhei Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan

Given two graphs, SUBGRAPH ISOMORPHISM is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time. In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Subgraph isomorphism Graph class polynomial-time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for special cases of the maximum confluent flow problem

引用

DISCRETE APPLIED MATHEMATICS 2014年第PART 2期163卷 142-154页

作者： Dressler, Daniel Strehler, Martin TU Berlin Inst Math D-10623 Berlin Germany Brandenburg Tech Univ Cottbus Math Inst D-03013 Cottbus Germany

A flow on a directed network is said to be confluent if the flow uses at most one outgoing arc at each node. Confluent flows arise naturally in destination-based routing. We study the maximum confluent flow problem (MAXCONF) with a single commodity but multiple sources and sinks and heterogeneous arc capacities. It was recently shown that MAXCONF is N P-hard even on trees. We improve the classification of easy and hard confluent flow problems by providing polynomial-time algorithms for outerplanar graphs with a single sink, as well as trees with a constant number of either sources or sinks. Furthermore, we present an FPTAS for graphs with bounded treewidth. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Confluent flow Outerplanar graph polynomial-time algorithm Treewidth FPTAS

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for linear and convex optimization on jump systems

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2007年第2期21卷 504-522页

作者： Shioura, Akiyoshi Tanaka, Ken'ichiro Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 980 Japan Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 113 Japan

The concept of a jump system, introduced by Bouchet and Cunningham [SIAM J. Discrete Math., 8 (1995), pp. 17-32], is a set of integer points with a certain exchange property. In this paper, we discuss several linear and convex optimization problems on jump systems and show that these problems can be solved in polynomial time under the assumption that a membership oracle for a jump system is available. We first present a polynomial-time implementation of the greedy algorithm for the minimization of a linear function. We then consider the minimization of a separable-convex function on a jump system and propose the. first polynomial-time algorithm for this problem. The algorithm is based on the domain reduction approach developed in Shioura [Discrete Appl. Math., 84 (1998), pp. 215-220]. We. finally consider the concept of M-convex functions on constant-parity jump systems which has been recently proposed by Murota [SIAM J. Discrete Math., 20 (2006), pp. 213-226]. It is shown that the minimization of an M-convex function can be solved in polynomial time by the domain reduction approach.

关键词： jump system discrete convex function bisubmodular function bisubmodular polyhedron polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial-time server allocation algorithm in delay-sensitive internet-of-things monitoring services

引用

COMPUTER NETWORKS 2024年 248卷

作者： Imanaka, Shoya Kawabata, Akio Chatterjee, Bijoy Chand Oki, Eiji Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Toyohashi Univ Technol Toyohashi Aichi 4418580 Japan South Asian Univ Dept Comp Sci New Delhi 110068 India

This paper proposes a polynomial -time algorithm for a server allocation problem in delay -sensitive Internet -ofThings (IoT) monitoring services. The server allocation problem determines the appropriate servers to which the database and application are allocated to minimize the maximum delay between the latest update of reference data and the start of application processing for monitoring data. The server allocation problem was previously handled by expressing it as an integer linear programming (ILP) problem. Nevertheless, it fails to meet the computational time complexity needed to solve the problem, and it does not offer a more efficient technique than the ILP approach. The proposed algorithm consists of two components. The first step entails choosing utilization servers for both the database and the application. Next, the second phase entails matching each usage server and its corresponding IoT device. We prove that the proposed algorithm obtains an optimal solution in polynomial time. We compare computation times between the ILP approach and the proposed algorithm. Numerical results show that the proposed algorithm obtains the optimal solution faster than the ILP approach.

关键词： Server allocation problem Internet of things Monitoring service polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time dynamic programming algorithm for an optimal picking problem in automated warehouses

引用

JOURNAL OF SCHEDULING 2024年第4期27卷 393-407页

作者： Barbato, Michele Ceselli, Alberto Righini, Giovanni Univ Milan Dipartimento Informat Giovanni Antoni Via Celoria 18 I-20133 Milan Italy

We consider an optimization problem arising when a set of items must be selected and picked up from given locations in an automated storage and retrieval system by a crane of given capacity, minimizing the overall distance traveled. The problem has been classified as open in a recent taxonomy of optimal picking problems in automated warehouses. In this paper, we analyze some non-trivial properties of the problem and we describe a polynomial-time dynamic programming algorithm to solve it to proven optimality.

关键词： Combinatorial optimization Crane scheduling polynomial-time algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：