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

COMPARISON OF NONPARAMETRIC ESTIMATORS FOR THE RENEWAL FUNCTION

JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES C-APPLIED STATISTICS 1990年第1期39卷 55-61页

作者： SCHNEIDER, H LIN, BS OCINNEIDE, C UNIV ARKANSAS FAYETTEVILLE AR 72701 USA

This paper addresses the problem of nonparametric estimation of the renewal function. Two estimators are discussed. The first estimator, introduced by Frees, is based on the sum of the ‘convolutions without replacement’ of the empirical distribution function. We suggest a polynomial time algorithm to compute this estimator. The second estimator is based on the renewal function of the empirical distribution. We show how this estimator may be computed efficiently by solving a discretized renewal equation. In a simulation study we show that the estimator based on the renewal equation has a slightly higher bias than the estimator introduced by Frees, while the mean-squared errors are about the same. However, the computing time for the new estimator suggested in this paper is generally much smaller than that for Frees’s estimator.

关键词： Failure times Nonparametric estimator polynomial time algorithm Renewal function

来源：评论

学校读者我要写书评

暂无评论

Finding gale strings

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 1065-1072页

作者： Casetti, Marta M. Merschen, Julian von Stengel, Bernhard Dept. of Mathematics London School of Economics London WC2A 2AE United Kingdom

The problem 2-. Nash of finding a Nash equilibrium of a bimatrix game belongs to the complexity class PPAD. This class comprises computational problems that are known to have a solution by means of a path-following argument. For bimatrix games, this argument is provided by the Lemke-Howson algorithm. It has been shown that this algorithm is worst-case exponential with the help of dual cyclic polytopes, where the algorithm can be expressed combinatorially via labeled bitstrings defined by the "Gale evenness condition" that characterize the vertices of these polytopes. We define the combinatorial problem Another completely labeled Gale string whose solutions define the Nash equilibria of games defined by cyclic polytopes, including games where the Lemke-Howson algorithm takes exponential time. If this problem was PPAD-complete, this would imply that 2-. Nash is PPAD-complete, in a much simpler way than the currently known proofs, including the original proof by Chen and Deng [Chen, X., and X. Deng (2006). Settling the complexity of two-player Nash equilibrium. Proc. 47th FOCS, 261-272]. However, we show that Another completely labeled Gale string is solvable in polynomial time by a simple reduction to Perfect matching in graphs, making it unlikely to be PPAD-complete. Although this result is negative, we hope that it stimulates research into combinatorially defined problems that are PPAD-complete and imply this property for 2-. Nash. © 2010 Elsevier B.V.

关键词： Complexity Gale Evenness Strings Lemke-Howson Nash Equilibria Perfect Matching polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving Some Instances of the 2-Color Problem

Solving Some Instances of the 2-Color Problem

引用

15th International Conference on Discrete Geometry for Computer Imagery

作者： Brocchi, S. Frosini, A. Rinaldi, S. Univ Florence Dipartimento Sistemi & Informat Florence Italy Univ Siena Dept Sci Math & Informat Siena Italy

ISBN: (纸本)9783642043963

In the held of Discrete Tomography, the 2-color problem consists in determining a matrix whose elements are of two different types, starting from its horizontal and vertical projections. It is known that the one color problem has a polynomial time reconstruction algorithm, while, with k >= 2, the k-color problem is NP-complete. Thus, the 2-color problem constitutes an interesting example of a problem just in the frontier between hard and easy problems. In this paper we define a linear time algorithm to solve a set of its instances, where some values of the horizontal and vertical projections are constant, while the others are upper bounded by a positive number proportional to the dimension of the problem. Our algorithm relies on classical studies for the solution of the one color problem.

关键词： Discrete tomography polynomial time algorithm k-color problem

来源：评论

学校读者我要写书评

暂无评论

Routing and Scheduling Problems with Two Agents on a Line-Shaped Network 1

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Yan, Hao Lu, Xiwen East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

ISBN: (数字)9783030926816

ISBN: (纸本)9783030926816;9783030926809

We consider routing and scheduling problems with two agents on a line-shaped network in this paper. There are two agents and each agent has some jobs which are located in the network. Let L = (V, E) be a line-shaped network, where V = {v(0)} boolean OR V-A boolean OR V-B is the set of n + 1 vertices and E is a set of edges. A job v is located at some vertex v, which is also denoted as v. The travel time d(u, v) is associated with each edge {u, v} is an element of E. The vehicle starts from an initial vertex v(0) is an element of V and visits all jobs for their processing. The objective is to find a route of the vehicle that minimizes the completion time of agent A under the constraint condition that the completion time of agent B is no more than the threshold value Q. We express this problem as line - 1 vertical bar C-max(B) <= Q vertical bar C-max(A). For the problem without release time, an O(n) time algorithm is provided. For the problem with release time, we show that this problem is NP-hard even though there is only one job in agent B and the jobs in agent A have no release time. Finally we give a (3, 3)-approximation algorithm for the before general problem.

关键词： Network scheduling Agent scheduling polynomial time algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial traffic demand polytope partitioning

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 1113-1120页

作者： Ben-Ameur, Walid Zotkiewicz, Mateusz Institut TELECOM TELECOM SudParis Samovar CNRS UMR 5157 91011 Évry Cedex 9 rue Charles Fourier France Institut TELECOM TELECOM SudParis Samovar CNRS UMR 5157 91011 Évry Cedex 9 rue Charles Fourier France Institute of Telecommunications Warsaw University of Technology 00-665 Warszawa Nowowiejska 15/19 Poland

We consider the problem of partitioning of a traffic demand polytope using a hyper-plane. The polytope is divided into parts, and different routing schemes are applied while dealing with traffic matrices from different parts of the polytope. Different demands cannot share resources, and reservation vectors on opposite sides of the hyperplane have to be identical. We provide a polynomial time algorithm solving the presented problem when a traffic demand polytope is defined as a convex hull of a known set of traffic demand matrices. © 2010 Elsevier B.V.

关键词： Polyhedral traffic model polynomial time algorithm Robust routing

来源：评论

学校读者我要写书评

暂无评论

algorithms and Complexity of Strongly Stable Non-crossing Matchings 9th

Algorithms and Complexity of Strongly Stable Non-crossing Ma...

引用

9th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Panda, B. S. Sachin Indian Inst Technol Delhi Dept Math New Delhi 110016 India

ISBN: (纸本)9783031252105;9783031252112

A matching is called stable if it has no blocking pair, where a blocking pair is a man-woman pair, say (m, w), such that m and w are not matched with each other in the matching but if they get matched with each other, then both of them become better off. A matching is called non-crossing if it does not admit any pair of edges that cross each other when all men and women are arranged in two parallel vertical lines with men on one line and women on the other. Two notions of matchings that are stable as well as non-crossing have been identified in the literature, namely (i) weakly stable non-crossing matching (WSNM) and (ii) strongly stable non-crossing matching (SSNM). An SSNM is a non-crossing matching which is stable in the classical sense, whereas in a WSNM, a blocking pair satisfies an extra condition that it must not cross any matching edge. It is known that the problem of finding a WSNM, which always exists in an SMI instance, is polynomial time solvable. However, the problem of determining the existence of an SSNM in SMTI is known to be NP-complete. We show that this problem is fixed-parameter tractable (FPT) when parameterized by total length of ties. We introduce a new notion of stable non-crossing matching, namely semi-strongly stable non-crossing matching (SSSNM). We prove that the problem of determining the existence of an SSSNM in SMI is NP-complete even if size of every man's preference list is at most two. On the positive side, we show that this problem is polynomial time solvable if every man's preference list contains at most one woman.

关键词： Stable non-crossing matching polynomial time algorithm NP-complete Fixed-parameter tractable (FPT)

来源：评论

学校读者我要写书评

暂无评论

On Encoders for Quantum Convolutional Codes

On Encoders for Quantum Convolutional Codes

引用

IEEE Information Theory Workshop (ITW)

作者： Grassl, Markus Roetteler, Martin Natl Univ Singapore Ctr Quantum Technol S1503-113 Sci Dr 2 Singapore 117543 Singapore NEC Lab Amer Princeton NJ 08540 USA

ISBN: (纸本)9781424482641

We consider the problem of computing an encoding circuit for a quantum convolutional code given by a polynomial stabilizer matrix S(D) = (X(D) vertical bar Z(D)). We present an algorithm that is very similar to a polynomial-time algorithm for computing the Smith form of a polynomial matrix. This is a step towards the conjecture that any quantum convolutional code has an encoder with polynomially bounded depth.

关键词： convolutional codes encoding encoding circuit polynomial matrices polynomial matrix polynomial stabilizer matrix polynomial time algorithm quantum convolutional code

来源：评论

学校读者我要写书评

暂无评论

Linear-time counting algorithms for independent sets in chordal graphs 1

引用

31st International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Okamoto, Y Uno, T Uehara, R Toyohashi Univ Technol Dept Informat & Comp Sci Tempa Ku Toyohashi Aichi 4418580 Japan Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan JAIST Sch Informat Sci Ishikari Hokkaido 9231292 Japan

ISBN: (数字)9783540314684

ISBN: (纸本)3540310002

We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets;(2) a linear-time algorithm for counting the number of maximum independent sets;(3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant amortized time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets;(2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.

关键词： chordal graph counting enumeration independent set NP-completeness #P-completeness polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs 32

New Geometric Representations and Domination Problems on Tol...

引用

32nd International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Giannopoulou, Archontia C. Mertzios, George B. Univ Durham Sch Engn & Comp Sci Durham England

ISBN: (纸本)9783939897781

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain amount of overlap without being in conflict. In one of the most natural generalizations of tolerance graphs with direct applications in the comparison of DNA sequences from different organisms, namely multitolerance graphs, two tolerances are allowed for each interval - one from the left and one from the right side. Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance and multitolerance graphs. In spite of this progress, the complexity status of some fundamental algorithmic problems on tolerance and multitolerance graphs, such as the dominating set problem, remained unresolved until now, three decades after the introduction of tolerance graphs. In this article we introduce two new geometric representations for tolerance and multitolerance graphs, given by points and line segments in the plane. Apart from being important on their own, these new representations prove to be a powerful tool for deriving both hardness results and polynomial time algorithms. Using them, we surprisingly prove that the dominating set problem can be solved in polynomial time on tolerance graphs and that it is APX-hard on multitolerance graphs, solving thus a longstanding open problem. This problem is the first one that has been discovered with a different complexity status in these two graph classes. Furthermore we present an algorithm that solves the independent dominating set problem on multitolerance graphs in polynomial time, thus demonstrating the potential of this new representation for further exploitation via sweep line algorithms.

关键词： tolerance graphs multitolerance graphs geometric representation dominating set problem polynomial time algorithm APX-hard

来源：评论

学校读者我要写书评

暂无评论

Pairwise disjoint paths in pancake graphs

Pairwise disjoint paths in pancake graphs

引用

8th International Conference on Parallel and Distributed Computing, Applications and Technologies

作者： Sawada, Naoki Kaneko, Keiichi Peng, Shietung Tokyo Univ Agr & Technol Grad Sch Engn Koganei Tokyo 1848588 Japan Hosei Univ Fac Comp & Informat Sci Tokyo 1848584 Japan

ISBN: (纸本)9780769530499

Disjoint paths problems have attracted much attention due to its numerous applications in fault-tolerant routing. The pairwise disjoint paths problem is one of them. In this paper, we propose an algorithm for the pairwise disjoint paths problem in an pancake graph. The algorithm can find k disjoint paths in an n-pancake graph where k <= left perpendicular n/2 right perpendicular. The k disjoint paths can be constructed in O(kn) time and the maximum path length is bounded by left perpendicular 5n/3 right perpendicular + 6.

关键词： interconnection networks polynomial time algorithm disjoint paths

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：