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

14th IEEE International Conference on Data Mining (IEEE ICDM)

作者： Pandey, Shishir Vaze, Rahul Tata Inst Fundamental Res Sch Technol & Comp Sci Bombay Maharashtra India

ISBN: (纸本)9781479943036

Given a large dimensional input and output space, even simple regression is prohibitively costly. Dimensionality reduction in the output space is important for efficient learning and prediction as modern paradigms, e.g. topic modelling, image classification, etc., have extremely large output spaces. In contrast to input dimensionality reduction, dimension reduction in output side is complicated. We propose, mutual information based output dimensionality reduction, that takes into account the relationship between the input and the output which is essential for regression and classification problems. Our method selects those labels to form the compressed label space that typically have the maximum mutual information with the input. Selecting the best subset is computationally hard, but we provide a polynomial time algorithm with provable approximation guarantee. We conduct experiments on seven multi-label classification datasets. Results show our method performs better than existing methods on some datasets.

关键词： approximation theory computational complexity learning (artificial intelligence) pattern classification regression analysis approximation guarantee classification problems compressed label space dimensional input space dimensional output space learning multilabel classification datasets mutual information based output dimensionality reduction polynomial time algorithm prediction regression problems subset selection Approximation methods Compressed sensing Decoding Educational institutions Greedy algorithms Mutual information Vectors dimension reduction multi-label mutual information output dimension reduction submodular function

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Envy-Free Matchings with Lower Quotas 28

Envy-Free Matchings with Lower Quotas

引用

28th International Symposium on algorithms and Computation (ISAAC)

作者： Yokoi, Yu Natl Inst Informat Tokyo 1018430 Japan

ISBN: (纸本)9783959770545

While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property. In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas and not all doctor-hospital pairs are acceptable. We first provide an algorithm that decides whether a given HR-LQ instance has an envy-free matching or not. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (in: Procedings of 21st annual ACM-SIAM symposium on discrete algorithms (SODA2010), SIAM, Philadelphia, pp 1235-1253, 2010), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.

关键词： Stable matchings Envy-free matchings Lower quotas polynomial time algorithm Paramodular functions

来源：评论

学校读者我要写书评

暂无评论

Container problem in burnt pancake graphs

Container problem in burnt pancake graphs

引用

3rd International Conference on Parallel and Distributed Processing and Applications

作者： Sawada, N Suzuki, Y Kaneko, K Tokyo Univ Agr & Technol Tokyo 1848588 Japan

ISBN: (纸本)3540297693

In this paper, we propose an algorithm that solves the container problem in n-burnt pancake graphs in polynomial order time of n. Its correctness is proved and estimates of time complexity and sum of paths lengths are given. We also report the results of computer experiment conducted to measure the average performance of our algorithm.

关键词： burnt pancake graphs container problem internally disjoint paths polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Capacity Expansion Problem of Strongly Connected Spanning Subgraph with Constraints 3

Capacity Expansion Problem of Strongly Connected Spanning Su...

引用

3rd International Conference on Industrial IoT, Big Data and Supply Chain (IIoTBDSC)

作者： Yang, Zilan Li, Rui Chen, Bin Lijiang Cultural & Tourism Coll Sch Informat Lijiang Peoples R China

ISBN: (纸本)9781665454551

Based on the congestion problem faced by flow transmission equipment in communication networks, in this paper, the capacity expansion problem of strongly connected spanning subgraph with constraints (CEPSCSSC) in directed networks is proposed. Firstly, NP-hardness is analyzed via Hamiltonian cycle problem. Secondly, a strongly connected spanning subgraph G' is constructed by looking for an inverse spanning arborescence and a spanning arborescence with the same root vertex through using Chu-Liu-Edmonds algorithm, and then G' is modified until the constraint conditions are satisfied by using the basic transformation of the spanning arborescence and the inverse spanning arborescence. so a heuristic algorithm, using the idea of arc exchange with the minimum weight increment, is designed to solve the CEPSCSSC problem. Finally, it is proved that the heuristic algorithm is correct and its time complexity is O (mnlogn).

关键词： strongly communication network connected subgraph NP-hard heuristic algorithm polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Network Flow Models for Days Off Scheduling 9th

Network Flow Models for Days Off Scheduling

引用

9th International Conference on Metaheuristics and Nature Inspired Computing (META)

作者： Tlig, Ghassen Jarray, Fethi Ecole Super Elect Ouest Paris France UTM Univ LIMTIC Lab Tunis Tunisia

ISBN: (纸本)9783031692567;9783031692574

This paper studies the days off scheduling problem when the demand for staffing may differ from day to another and when the total load is fixed in advance for each employee. The scheduling problem is then to assign on-days and days-off to employees with different objectives: (1) exactly met the demand and the offer requirement (2) satisfy as best as possible the requirements. For each one, we propose a polynomial time algorithm based on network flow to construct a feasible scheduling.

关键词： Workforce Scheduling Maximum Flow polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：