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

An algorithm for the secure total domination problem in proper interval graphs

THEORETICAL COMPUTER SCIENCE 2024年 1011卷

作者： Araki, Toru Aita, Yasufumi Gunma Univ Fac Informat Maebashi Gunma 3718510 Japan Gunma Univ Div Elect & Informat Kiryu Gunma 3768515 Japan

A subset S of vertices of G is a total dominating set if, for any vertex v , there is a vertex in S adjacent to v . A total dominating set S is a secure total dominating set if, for any vertex v is not an element of S , there is a vertex u ES such that uv is an edge and (S \ {u}) U {v} is also a total dominating set. In this paper, we design an O(m)-time algorithm for computing a minimum secure total dominating set in a proper interval graph, where m is the number of edges.

关键词： Secure total dominating set Dominating set Total dominating set Proper interval graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Refined Computational Complexities of Hospitals/Residents Problem with Regional Caps 28th

Refined Computational Complexities of Hospitals/Residents Pr...

引用

28th International Computing and Combinatorics Conference (COCOON)

作者： Hamada, Koki Miyazaki, Shuichi NTT Social Informat Labs 3-9-11 Midori Cho Musashino Tokyo 1808585 Japan Univ Hyogo Nishi Ku 8-2-1 Gakuennishi Machi Kobe Hyogo 6512197 Japan

ISBN: (纸本)9783031221040;9783031221057

The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resolve imbalance in the number of residents assigned to hospitals, an extension called HR with regional caps (HRRC) was introduced. In this problem, a positive integer (called a regional cap) is associated with a subset of hospitals (called a region), and the total number of residents assigned to hospitals in a region must be at most its regional cap. Kamada and Kojima [11,13] defined strong stability for HRRC and demonstrated that a strongly stable matching does not necessarily exist. Recently, Aziz et al. [3] proved that the problem of determining if a strongly stable matching exists is NP-complete in general. In this paper, we refine Aziz et al.'s result by investigating the computational complexity of the problem in terms of the length of preference lists, the size of regions, and whether or not regions can overlap, and completely classify tractable and intractable cases.

关键词： Hospitals/residents problem Stable matching Strong stability Regional cap Computational complexity polynomial-time algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

The Shortest Even Cycle Problem Is Tractable 2022

The Shortest Even Cycle Problem Is Tractable

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Bjorklund, Andreas Husfeldt, Thore Kaski, Petteri Lund Univ Lund Sweden IT Univ Copenhagen Copenhagen Denmark Aalto Univ Dept Comp Sci Espoo Finland

ISBN: (纸本)9781450392648

Given a directed graph as input, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was previously known for this problem. In fact, finding any even cycle in a directed graph in polynomial time was open for more than two decades until Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004;announced jointly at STOC 1997) gave an efficiently testable structural characterisation of even-cycle-free directed graphs. Methodologically, our algorithm relies on the standard framework of algebraic fingerprinting and randomized polynomial identity testing over a finite field, and in fact relies on a generating polynomial implicit in a paper of Vazirani and Yannakakis (Discrete Appl. Math. 1989) that enumeratesweighted cycle covers by the parity of their number of cycles as a difference of a permanent and a determinant polynomial. The need to work with the permanent- known to be #P-hard apart from a very restricted choice of coefficient rings (Valiant, Theoret. Comput. Sci. 1979)-is where our main technical contribution occurs. We design a family of finite commutative rings of characteristic 4 that simultaneously (i) give a nondegenerate representation for the generating polynomial identity via the permanent and the determinant, (ii) support efficient permanent computations by extension of Valiant's techniques, and (iii) enable emulation of finite-field arithmetic in characteristic 2. Here our work is foreshadowed by that of Bjorklund and Husfeldt (SIAM J. Comput. 2019), who used a considerably less efficient commutative ring design-in particular, one lacking finite-field emulation-to obtain a polynomial-time algorithm for the shortest two disjoint paths problem in undirected graphs. Building on work of Gilbert and Tarjan (Numer. Math. 1978) as well as Alon and Yuster (J. ACM 2013), we also show how ideas from the nested dissect

关键词： directed graph shortest even cycle shortest two disjoint paths parity cycle cover permanent polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The Implication Problem for Functional Dependencies and Variants of Marginal Distribution Equivalences 1

引用

12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS)

作者： Hirvonen, Minna Univ Helsinki Dept Math & Stat Helsinki Finland

ISBN: (数字)9783031113215

ISBN: (纸本)9783031113215;9783031113208

We study functional dependencies together with two different probabilistic dependency notions: unary marginal identity and unary marginal distribution equivalence. A unary marginal identity states that two variables x and y are identically distributed. A unary marginal distribution equivalence states that the multiset consisting of the marginal probabilities of all the values for variable x is the same as the corresponding multiset for y. We present a sound and complete axiomatization and a polynomial-time algorithm for the implication problem for the class of these dependencies, and show that this class has Armstrong relations.

关键词： Armstrong relations Complete axiomatization Functional dependence Marginal distribution equivalence polynomial-time algorithm Probabilistic team semantics

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms and Hardness Results for Geometric Red-Blue Hitting Set Problem

Exact Algorithms and Hardness Results for Geometric Red-Blue...

引用

3rd International Joint Conference on Theoretical Computer Science (IJTCS) / 16th International Conference on Frontiers of algorithmic Wisdom (FAW)

作者： Madireddy, Raghunath Reddy Nandy, Subhas C. Pandit, Supantha Birla Inst Technol & Sci Pilani Hyderabad Campus Hyderabad Telangana India Indian Stat Inst Kolkata India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

ISBN: (纸本)9783031207952;9783031207969

We study geometric variations of the Red-Blue Hitting Set problem. Given two sets of objects R and B, colored red and blue, respectively, and a set of points P in the plane, the goal is to find a subset P ' subset of P of points that hits all blue objects in B while hitting the minimum number of red objects in R. We study this problem for various geometric objects. We present a polynomial-time algorithm for the problem with intervals on the real line. On the other hand, we show that the problem is NP-hard for axis-parallel unit segments. Next, we study the problem with axis-parallel rectangles. We give a polynomial-time algorithm for the problem when the rectangles are anchored on a horizontal line. The problem is shown to be NP-hard when all the rectangles intersect a horizontal line. Finally, we prove that the problem is APX-hard when the objects are axis-parallel rectangles containing the origin of the plane, axis-parallel rectangles where every two rectangles intersect exactly either zero or four times, axis-parallel line segments, axis-parallel strips, and downward shadows of segments. To achieve these APX-hardness results, we first introduce a variation of the Red-Blue Hitting Set problem in a set system, called the Special-Red-Blue Hitting Set problem. We prove that the Special-Red-Blue Hitting Set problem is APX-hard and we provide an encoding of each class of objects mentioned above as the Special-Red-Blue Hitting Set problem.

关键词： Special Red-Blue Hitting Set Anchored rectangles Intervals polynomial-time algorithm NP-hard APX-hard

来源：评论

学校读者我要写书评

暂无评论

Clustering with Queries under Semi-Random Noise 35

Clustering with Queries under Semi-Random Noise

引用

35th Conference on Learning Theory (COLT)

作者： Del Pia, Alberto Ma, Mingchen Tzamos, Christos Univ Wisconsin Madison Madison WI 53706 USA

The seminal paper by Mazumdar and Saha (2017a) introduced an extensive line of work on clustering with noisy queries. Yet, despite significant progress on the problem, the proposed methods depend crucially on knowing the exact probabilities of errors of the underlying fully-random oracle. In this work, we develop robust learning methods that tolerate general semi-random noise obtaining qualitatively the same guarantees as the best possible methods in the fully-random model. More specifically, given a set of n points with an unknown underlying partition, we are allowed to query pairs of points u;v to check if they are in the same cluster, but with probability p, the answer may be adversarially chosen. We show that information theoretically O(nk log n/(1 -2 p)(2) queries suffice to learn any cluster of sufficiently large size. Our main result is a computationally efficient algorithm that can identify large clusters with O(nk log n/((1 - 2p)(2)) + poly (log n, k, 1/1 -2(p)) queries, matching the guarantees of the best known algorithms in the fully-random model. As a corollary of our approach, we develop the first parameter-free algorithm for the fully-random model, answering an open question in Mazumdar and Saha (2017a).

关键词： Clustering Semi-random noise 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：