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

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

来源：评论

学校读者我要写书评

暂无评论

Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第12期67卷 8109-8139页

作者： Gamarnik, David Kizildag, Eren C. Zadik, Ilias MIT Sloan Sch Management 77 Massachusetts Ave Cambridge MA 02139 USA MIT Lab Informat & Decis Syst LIDS 77 Massachusetts Ave Cambridge MA 02139 USA NYU Ctr Data Sci CDS New York NY 10013 USA MIT Dept Math Cambridge MA 02139 USA

We consider the high-dimensional linear regression problem, where the algorithmic goal is to efficiently infer an unknown feature vector beta* is an element of R-p from its linear measurements, using a small number n of samples. Unlike most of the literature, we make no sparsity assumption on beta*, but instead adopt a different regularization: In the noiseless setting, we assume beta* consists of entries, which are either rational numbers with a common denominator Q is an element of Z(+) (referred to as Q-rationality);or irrational numbers taking values in a rationally independent set of bounded cardinality, known to learner;collectively called as the mixed-range assumption. Using a novel combination of the Partial Sum of Least Squares (PSLQ) integer relation detection, and the Lenstra-Lenstra-Lovasz (LLL) lattice basis reduction algorithms, we propose a polynomial-time algorithm which provably recovers a beta* is an element of R-p enjoying the mixed-range assumption, from its linear measurements Y = X beta* is an element of R-n for a large class of distributions for the random entries of X, even with one measurement (n = 1). In the noisy setting, we propose a polynomial-time, lattice-based algorithm, which recovers a beta* is an element of R-p enjoying the Q-rationality property, from its noisy measurements Y = X beta* +W is an element of R-n, even from a single sample (n = 1). We further establish that for large Q, and normal noise, this algorithm tolerates information-theoretically optimal level of noise. We then apply these ideas to develop a polynomial-time, single-sample algorithm for the phase retrieval problem. Our methods address the single-sample (n = 1) regime, where the sparsity-based methods such as the Least Absolute Shrinkage and Selection Operator (LASSO) and the Basis Pursuit are known to fail. Furthermore, our results also reveal algorithmic connections between the high-dimensional linear regression problem, and the integer relation detection, ran

关键词： High-dimensional statistical inference linear regression phase retrieval lattices integer relation detection subset sum problem polynomial-time algorithm single-sample recovery information-theoretic thresholds channel capacity

来源：评论

学校读者我要写书评

暂无评论

NEIGHBOR SYSTEMS, JUMP SYSTEMS, AND BISUBMODULAR POLYHEDRA

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2012年第1期26卷 114-144页

作者： Shioura, Akiyoshi Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

The concept of neighbor system, introduced by Hartvigsen in 2010, is a set of integral vectors satisfying a certain combinatorial property. In this paper, we reveal the relationship of neighbor systems with jump systems and with bisubmodular polyhedra. We first prove that for every neighbor system, there exists a jump system which has the same neighborhood structure as the original neighbor system. This shows that the concept of neighbor system is essentially equivalent to that of jump system. We next show that the convex closure of a neighbor system is an integral bisubmodular polyhedron. In addition, we give a characterization of neighbor systems using bisubmodular polyhedra. Finally, we consider the problem of minimizing a separable convex function on a neighbor system. It is shown that the problem can be solved in weakly polynomial time for a class of neighbor systems.

关键词： matroid polymatroid submodular function greedy algorithm polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for Rank-1 Bimatrix Games

引用

OPERATIONS RESEARCH 2021年第2期69卷 613-631页

作者： Adsul, Bharat Garg, Jugal Mehta, Ruta Sohoni, Milind von Stengel, Bernhard Indian Inst Technol Dept Comp Sci & Engn Mumbai 400076 Maharashtra India Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61801 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA London Sch Econ Dept Math London WC2A 2AE England

The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one and shows the following: (1) For a game of rank r, the set of its Nash equilibria is the intersection of a generically one-dimensional set of equilibria of parameterized games of rank r - 1 with a hyperplane. (2) One equilibrium of a rank-1 game can be found in polynomial time. (3) All equilibria of a rank-1 game can be found by following a piecewise linear path. In contrast, such a path-following method finds only one equilibrium of a bimatrix game. (4) The number of equilibria of a rank-1 game may be exponential. (5) There is a homeomorphism between the space of bimatrix games and their equilibrium correspondence that preserves rank. It is a variation of the homeomorphism used for the concept of strategic stability of an equilibrium component.

关键词： bimatrix game Nash equilibrium rank-1 game polynomial-time algorithm homeomorphism

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with a variable maintenance activity

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2015年 79卷 168-174页

作者： Luo, Wenchang Cheng, T. C. E. Ji, Min Ningbo Univ Fac Sci Ningbo 315211 Zhejiang Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhejiang Gongshang Univ Sch Comp Sci & Informat Engn Contemporary Business & Trade Res Ctr Hangzhou 310018 Zhejiang Peoples R China

We consider the problem maintenance activity must starting time. We provide sum of completion times, of scheduling a maintenance activity and jobs on a single machine, where the start before a given deadline and the maintenance duration increases with its polynomial-time algorithms to solve the problems to minimize the makespan, maximum lateness, and number of tardy jobs. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Scheduling Maintenance Single machine polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

George Dantzig's impact on the theory of computation

引用

DISCRETE OPTIMIZATION 2008年第2期5卷 174-185页

作者： Karp, Richard M. Univ Calif Berkeley Dept Elect Engn & Comp Sci Div Comp Sci Berkeley CA 94720 USA Int Comp Sci Inst Berkeley CA 94704 USA

George Dantzig created the simplex algorithm for linear programming, perhaps the most important algorithm developed in the 20th century. This paper traces a single historical thread: Dantzig's work on linear programming and its application and extension to combinatorial optimization, and the investigations it has stimulated about the performance of the simplex algorithm and the intrinsic complexity of linear programming and combinatorial optimization. (c) 2007 Elsevier B.V. All rights reserved.

关键词： linear programming simplex algorithm combinatorial optimization integer programming computational complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

MATCHING PROBLEMS WITH DELTA-MATROID CONSTRAINTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第2期28卷 942-961页

作者： Kakimura, Naonori Takamatsu, Mizuyo Univ Tokyo Coll Arts & Sci Tokyo 1538902 Japan Chuo Univ Dept Informat & Syst Engn Tokyo 1128551 Japan

Given an undirected graph G = (V, E) and a delta-matroid (V, F), the delta-matroid matching problem is to find a maximum cardinality matching M such that the set of the end vertices of M belongs to F. This problem is a natural generalization of the matroid matching problem to delta-matroids, and thus it cannot be solved in polynomial time in general. This paper introduces a class of the delta-matroid matching problem, where the given delta-matroid is a projection of a linear delta-matroid. We first show that it can be solved in polynomial time if the given linear delta-matroid is generic. This result enlarges a polynomially solvable class of matching problems with precedence constraints on vertices such as the 2-master/slave matching. In addition, we design a polynomial-time algorithm when the graph is bipartite and the delta-matroid is defined on one vertex side. This result is extended to the case where a linear matroid constraint is additionally imposed on the other vertex side.

关键词： constrained matching delta-matroid polynomial-time algorithm mixed matrix theory

来源：评论

学校读者我要写书评

暂无评论

Distributionally robust Weber problem with uncertain demand

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2023年第3期85卷 705-752页

作者： Gu, Yan Jiang, Jianlin Zhang, Shun Nanjing Univ Aeronaut & Astronaut Coll Math Nanjing 210016 Peoples R China

Weber problem is an important model in facility location field, and it can be modeled as a stochastic problem when the future demand of customers is uncertain. By minimizing the maximal expectation of the objective on an ambiguity set, the distributionally robust optimization (DRO) can utilize the valuable information from historical data and thus it has become an attractive formulation for stochastic problems. In this paper, an extended moment-based DRO formulation and a polynomial-time algorithm are contributed to solving the Weber problem with uncertain demand. Specifically, by constructing a new ambiguity set, which is proved to contain the true distribution with high probability, an extended DRO formulation allowing positive semidefinite covariance matrix is first built for general stochastic problems. To obtain a more robust solution, the Weber problem is then reformulated into an equivalent stochastic variational inequality (SVI). Following the extended DRO formulation, a distributionally robust Weber problem (DRWP) is further developed with minimizing the expectation of a residual function of the SVI. The DRWP can be transformed to a semidefinite program (SDP) with an undesired exponential number of constraints. Through the adoption of a plane decomposition technique, a simple algorithm is proposed to solve the resulted SDP and obtain the optimal solution to DRWP in polynomial time. Some preliminary numerical results demonstrate the effectiveness of the proposed DRWP and algorithm.

关键词： Distributionally robust optimization Positive semidefinite covariance matrix Stochastic variational inequality polynomial-time algorithm Alternating direction method of multipliers Plane decomposition technique

来源：评论

学校读者我要写书评

暂无评论

Some graph optimization problems with weights satisfying linear constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期43卷 200-225页

作者： Nip, Kameng Wang, Zhenbo Shi, Tianning Xiamen Univ Sch Math Sci Xiamen Peoples R China Tsinghua Univ Dept Math Sci Beijing Peoples R China

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including maximum matching problem under linear constraints (max-MLC), minimum perfect matching problem under linear constraints (min-PMLC), shortest path problem under linear constraints (SPLC) and vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and find the optimal solutions of corresponding graph optimization problems among all feasible choices of weights. We find that these problems are NP-hard and are hard to be approximated in general. These findings suggest us to explore various special cases of them. In particular, we show that when the number of constraints is a fixed constant, all these problems are polynomially solvable. Moreover, if the total number of distinct weights is a fixed constant, then max-MLC, min-PMLC and SPLC are polynomially solvable, and VCLC has a 2-approximation algorithm. In addition, we propose approximation algorithms for various cases of max-MLC.

关键词： Graph optimization Linear programming polynomial-time algorithm Approximation algorithm Computational complexity

来源：评论

学校读者我要写书评

暂无评论

New algorithms for weighted k-domination and total k-domination problems in proper interval graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 795卷 128-141页

作者： Chiarelli, Nina Romina Hartinger, Tatiana Alejandra Leoni, Valeria Lopez Pujato, Maria Ines Milanic, Martin Univ Primorska Fac Math Nat Sci & Informat Technol Glagoljaska 8 SI-6000 Koper Slovenia Univ Primorska Andrej Marusic Inst Muzejski Trg 2 SI-6000 Koper Slovenia Cognit Etermax Labs Estados Unidos 34Piso 7C11001AAB Buenos Aires DF Argentina Univ Nacl Rosario FCEIA Rosario Santa Fe Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina ANPCyT Buenos Aires DF Argentina

Given a positive integer k, a k-dominating set in a graph G is a set of vertices such that every vertex not in the set has at least k neighbors in the set. A total k-dominating set is a set of vertices such that every vertex of the graph has at least k neighbors in the set. The problems of finding the minimum size of a k-dominating, respectively total k-dominating set, in a given graph, are referred to as k-domination, respectively total k-domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total k-domination). On the other hand, it follows from previous works by Bui-Xuan et al. (2013) [8] and by Belmonte and Vatshelle (2013) [3] that these two families of problems are solvable in time O(vertical bar V(G)vertical bar(3 k+4)) in the class of interval graphs. We develop faster algorithms for k-domination and total k-domination in the class of proper interval graphs, by means of reduction to a single shortest path computation in a derived directed acyclic graph with O(vertical bar V(G)vertical bar(2k)) nodes and O(vertical bar V(G)vertical bar(4k)) arcs. We show that a suitable implementation, which avoids constructing all arcs of the digraph, leads to a running time of O(vertical bar V(G)vertical bar(3k)). The algorithms are also applicable to the weighted case. (C) 2019 Published by Elsevier B.V.

关键词： k-domination Total k-domination Proper interval graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：