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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the fast delivery problem with one or two packages

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 115卷 246-263页

作者： Carvalho, Iago A. Erlebach, Thomas Papadopoulos, Kleitos Univ Estadual Campinas Inst Comp Campinas Brazil Univ Fed Minas Gerais Dept Comp Sci Belo Horizonte MG Brazil Univ Leicester Sch Informat Leicester Leics England

We study two problems where k autonomous mobile agents are initially located on distinct nodes of a weighted graph with nnodes and medges. Each agent has a predefined velocity and can only move along the edges of the graph. The first problem is to deliver one package from a source node to a destination node. The second is to simultaneously deliver two packages, each from its source node to its destination node. These deliveries are achieved by the collective effort of the agents, which can carry and exchange a package among them. For one package, we propose an O(kn logn + km) time algorithm for computing a delivery schedule that minimizes the delivery time. For two packages, we show that the problem of minimizing the maximum or the sum of the delivery times is NP-hard for arbitrary agent velocities, but polynomial-time solvable for agents with equal velocity. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Mobile agents Dijkstra's algorithm polynomial-time algorithm time-dependent shortest paths NP-hardness

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Linear Arboricity of Outer-1-Planar Graphs

引用

Journal of the Operations Research Society of China 2021年第1期9卷 181-193页

作者： Xin Zhang Bi Li School of Mathematics and Statistics Xidian UniversityXi’an 710071China

A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most *** et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Math 312:2788-2799,2012;MR2945171)proved that the linear arboricity of every outer-1-planar graph with maximum degree△is exactly[△/2] provided that△=3or△≥5 and claimed that there are outer-1-planar graphs with maximum degree △=4 and linear arboricity[[(O+1)/2]=*** is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2,and moreover,none of the above constraints on the crossing distance and Crossing width can be removed..Besides,a polynomial-time algorithm for constructing a path-2-coloring(i.e.,an edge 2-coloring such that each color class induces a linear forest,a disjoint union of paths)of such an outer-1-planar drawing is given.

关键词： Outer-1-planar graph Crossing Linear arboricity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The Complexity of Growing a Graph 1

引用

18th International Symposium on algorithmics of Wireless Networks

作者： Mertzios, George B. Michail, Othon Skretas, George Spirakis, Paul G. Theofilatos, Michail Univ Durham Dept Comp Sci Durham England Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Potsdam Hasso Plattner Inst Potsdam Germany Univ Patras Comp Engn & Informat Dept Patras Greece

ISBN: (数字)9783031220500

ISBN: (纸本)9783031220494;9783031220500

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u(0) and operates in discrete time-steps, called slots. In every slot t >= 1, the process updates the current graph instance to generate the next graph instance G(t). The process first sets G(t) = G(t-1). Then, for every u is an element of V (G(t-1)), it adds at most one new vertex u' to V (G(t)) and adds the edge uu' to E(G(t)) alongside any subset of the edges {vu' vertical bar v is an element of V (G(t-1)) is at distance at most d - 1 from u in G(t-1)}, for some integer d >= 1 fixed in advance. The process completes slot t after removing any (possibly empty) subset of edges from E(G(t)). Removed edges are called excess edges. G(t) is the graph grown by the process after t slots. The goal of this paper is to investigate the algorithmic and structural properties of this process of graph growth. Graph Growth Problem: Given a graph family F, we are asked to design a centralized algorithm that on any input target graph G is an element of F, will output such a process growing G, called a growth schedule for G. Additionally, the algorithm should try to minimize the total number of slots k and of excess edges l used by the process. We show that the most interesting case is when d = 2 and that there is a natural trade-off between k and l. We begin by investigating growth schedules of l = 0 excess edges. On the positive side, we provide polynomial-time algorithms that decide whether a graph has growth schedules of k = logn or k = n - 1 slots. Along the way, interesting connections to cop-win graphs are being revealed. On the negative side, we establish strong hardness results for the problem of determining the minimum number of slots required to grow a graph with zero excess edges. In particular, we show that the problem (i) is NP-complete and (ii) for any e > 0, cannot be approximated within n(1/3-epsilon), unless P = NP. We then move our focus to the other extreme of the (

关键词： Temporal graph Cop-win graph Graph process polynomial-time algorithm Lower bound NP-complete Hardness result

来源：评论

学校读者我要写书评

暂无评论

The single train shortest route problem in a railyard

引用

OPTIMIZATION LETTERS 2021年第8期15卷 2577-2595页

作者： Aliakbari, Mina Geunes, Joseph Sullivan, Kelly M. Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA Univ Arkansas Dept Ind Engn Fayetteville AR 72701 USA

We consider the problem of moving a connected set of railcars, which we refer to as a train, from an origin layout to a destination layout in a railyard, accounting for the special structure of the railyard network and the length and orientation of the train. We propose a novel shortest path algorithm for determining a sequence of moves that minimizes the total distance (and associated time) required to move a train from its origin to destination. A railyard network consists of a set of track sections connected via switch points, which correspond to points at which three sections of track come together, such that one pair of the track segments forms an acute angle (and the other two pairs form obtuse angles). A train's ability to traverse a switch node depends on the train's length and whether or not its desired route involves traversing the acute angle or an obtuse angle at the switch. The shortest route problem for a train is further complicated by the fact that a train's position on the network at any point in time may span multiple nodes in the network. We propose an easily explained solution approach that addresses the complications associated with switch points and the train's length to determine a shortest route from origin to destination in O(e + n log n) operations, where n and e correspond to the number of switch nodes and edges in the network respectively.

关键词： Shortest path Railyard network Routing polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Strong cliques in diamond-free graphs

引用

THEORETICAL COMPUTER SCIENCE 2021年 858卷 49-63页

作者： Chiarelli, Nina Martinez-Barona, Berenice Milanic, Martin Monnot, Jerome Mursic, Peter Univ Primorska FAMNIT Glagoljaska 8 Koper 6000 Slovenia Univ Primorska IAM Muzejski Trg 2 Koper 6000 Slovenia Univ Politecn Cataluna Dept Engn Civil & Ambiental Barcelona Spain Univ Paris 09 LAMSADE Paris 16 France

A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or coNP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques? On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamondfree graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erd os-Hajnal property for such graphs. (c) 2020 Elsevier B.V. All rights reserved.

关键词： Maximal clique Maximal stable set Diamond-free graph Strong clique Simplicial clique Strongly perfect graph CIS graph NP-hard problem polynomial-time algorithm Erdos-Hajnal property

来源：评论

学校读者我要写书评

暂无评论

On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines

引用

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS 2021年第SUPPL 1期313卷 S58-S72页

作者： Gimadi, E. Kh. Tsidulko, O. Yu. Russian Acad Sci Sobolev Inst Math Siberian Branch Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

We study the network facility location problem with constraints on the capacities of communication lines, called Restricted Facility Location Problem (RFLP). It is required to locate facilities at the vertices of a given network graph so as to simultaneously satisfy at minimum cost the demands of customers located at the vertices of the graph. We consider two statements of the problem: the multiple allocation RFLP, where the demand of a customer can be satisfied jointly by several facilities, and the single allocation RFLP, where the demand of a customer must be entirely satisfied by a single facility. We show that the single allocation RFLP is NP-hard even if the network is a simple path and strongly NP-hard if the network is a tree. The multiple allocation RFLP is weakly NP-hard on trees. For this problem, we propose a pseudopolynomial-time algorithm for the case where the network graph has constant treewidth and a linear-time algorithm for the case where the network is a simple path.

关键词： facility location problem capacities multiple allocation single allocation NP-hard problem treewidth pseudopolynomial-time algorithm polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Complete Characterization of Incorrect Orthology Assignments in Best Match Graphs

引用

JOURNAL OF MATHEMATICAL BIOLOGY 2021年第3期82卷 1-64页

作者： Schaller, David Geiss, Manuela Stadler, Peter F. Hellmuth, Marc Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Univ Leipzig Dept Comp Sci Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Software Competence Ctr Hagenberg GmbH Softwarepk 21 A-4232 Hagenberg Austria Univ Leipzig Dept Comp SciInterdisciplinary Ctr Bioinformat German Ctr Integrat Biodivers Res IDiv Halle Jena Bioinformat GrpCompetence Ctr Scalable Data Serv Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Leipzig Res Ctr Civilizat Dis Hartelstr 16-18 D-04107 Leipzig Germany Univ Vienna Inst Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA Stockholm Univ Dept Math Fac Sci SE-10691 Stockholm Sweden

Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best match. Incorrect orthology assignments therefore are always false positives in the reciprocal best match graph. We consider duplication/loss scenarios and characterize unambiguous false-positive (u-fp) orthology assignments, that is, edges in the best match graphs (BMGs) that cannot correspond to orthologs for any gene tree that explains the BMG. Moreover, we provide a polynomial-time algorithm to identify all u-fp orthology assignments in a BMG. Simulations show that at least 75% of all incorrect orthology assignments can be detected in this manner. All results rely only on the structure of the BMGs and not on any a priori knowledge about underlying gene or species trees.

关键词： Orthology detection Best matches Unambiguous orthologs Colored graphs Cograph Tree reconciliation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：