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

combinatorial algorithms for Binary Operations on LR-tableaux with Entries Equal to 1 with Applications to Nilpotent Linear Operators

引用

FUNDAMENTA INFORMATICAE 2020年第2期174卷 121-136页

作者： Kaniecki, Mariusz Kosakowska, Justyna Nicolaus Copernicus Univ Fac Math & Comp Sci Chopina 12-18 PL-87100 Torun Poland

In the paper we investigate an algorithmic associative binary operation * on the set LR1 of Littlewood-Richardson tableaux with entries equal to one. We extend * to an algorithmic nonassociative binary operation on the set LR1 x N and show that it is equivalent to the operation of taking the generic extensions of objects in the category of homomorphisms from semisimple nilpotent linear operators to nilpotent linear operators. Thus we get a combinatorial algorithm computing generic extensions in this category.

关键词： Littlewood-Richardson tableaux partitions invariant subspaces nilpotent linear operators generic extensions pickets degeneration partial order combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

combinatorial algorithms for the unsplittable flow problem

引用

ALGORITHMICA 2006年第1期44卷 49-66页

作者： Azar, Y Regev, O Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

We provide combinatorial algorithms for the unsplittable flow problem (UFP) that either match or improve the previously best results. In the UFP we are given a (possibly directed) capacitated graph with n vertices and m edges, and a set of terminal pairs each with its own demand and profit. The objective is to connect a subset of the terminal pairs each by a single flow path subject to the capacity constraints such that the total profit of the connected pairs is maximized. We consider three variants of the problem. First is the classical UFP in which the maximum demand is at most the minimum edge capacity. It was previously known to have an O(root m) approximation algorithm;the algorithm is based on the randomized rounding technique and its analysis makes use of the Chernoff bound and the FKG inequality. We provide a combinatorial algorithm that achieves the same approximation ratio and whose analysis is considerably simpler. Second is the extended UFP in which some demands might be higher than edge capacities. Our algorithm for this case improves the best known approximation ratio. We also give a lower bound that shows that the extended UFP is provably harder than the classical UFP. Finally, we consider the bounded UFP in which the maximum demand is at most 1/K times the minimum edge capacity for some K>1. Here we provide combinatorial algorithms that match the currently best known algorithms. All of our algorithms are strongly polynomial and some can even be used in the online setting.

关键词： unsplittable flow problem combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties

引用

OPTIMIZATION LETTERS 2023年第8期17卷 1939-1956页

作者： Li, Jianping Cai, Lijian Lichen, Junran Pan, Pengxiang Yunnan Univ Sch Math & Stat East Outer Ring South Rd Kunming 650504 Peoples R China Beijing Univ Chem Technol Sch Math & Phys 15 North 3rd Ring East Rd Beijing 100029 Peoples R China

In this paper, we address the constrained knapsack problem with divisible item sizes and penalties (the CK-DSP problem, for short), which is modelled as follows. Given a set A = {a(1), a(2), ... , a(n)} of n items and a knapsack K with capacity L, where each item a(i) is an element of A has a size s(i) is an element of Z(+) , a profit c(i) is an element of R+ , a penalty pi is an element of R+, and these n item sizes are divisible, i.e., either s(i)|s(j )or s(j)|s(i) for any two distinct items a(i) and a(j) in A, each item a(i) is an element of A must be either put into K under the constraint that the summation of sizes of items in K does not exceed L, or rejected with its penalty pi that we must pay for, it is asked to find a subset X subset of A to satisfy the constraint s(X) = n-expressionry sumexpressiontion (ai is an element of X) s(i) <= L . We consider three versions of the CK-DSP problem, respectively. (1) The constrained knapsack problem with divisible item sizes and total penalties (the CK-DSTP problem, for short) is asked to find a subset X subset of A to satisfy the constraint s(X) <= L , the objective is to maximize the value of total profits of the items in X minus total penalties paid for the rejected items not in X;(2) The constrained knapsack problem with divisible item sizes and maximum penalty (the CK-DSMP problem, for short) is asked to find a subset X subset of A to satisfy the constraint s(X) <= L , the objective is to maximize the value of total profits of the items in X minus maximum penalty paid for the rejected items not in X;(3) The penalized knapsack problem with divisible item sizes (the PK-DS problem, for short) is asked to find a subset X subset of A to satisfy the constraint s(X) <= L , the objective is to maximize the value of total profits of the items in X minus maximum penalty paid for the items in X. As our contributions, we design three exact combinatorial algorithms to solve the CK-DSTP problem, the CK-DSMP problem and the PK-D

关键词： combinatorial optimization Knapsack problem Divisible item sizes Penalties combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

combinatorial algorithms for the minimum interval cost flow problem

引用

APPLIED MATHEMATICS AND COMPUTATION 2006年第2期175卷 1200-1216页

作者： Hashemi, S. Medhi Ghatee, Mehdi Nasrabadi, Ebrahim Amirkabir Univ Technol Fac Math & Comp Sci Tehran Iran

The aim of minimum the interval cost flow problem (MICFP) is to find the least cost of the shipment of a commodity through a capacitated network in order to satisfy demands at certain nodes from available supplies at other nodes where there exists some vague in vector cost of problem. Interval cost is a common event in uncertainty environments, where statistical data are applied. Moreover they almost play an essential role in fuzzy programming, specially in the case of using their cuts. In this paper, a complete order on intervals is defined and efficient combinatorial algorithms for MICFP are proposed. Digital simulation results show the performance of the proposed algorithms compared with real scenarios. (c) 2005 Elsevier Inc. All rights reserved.

关键词： minimum interval cost flow problem complete ordering combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

combinatorial algorithms and Methods for Security of Statistical Databases Related to the Work of Mirka Miller 28th

Combinatorial Algorithms and Methods for Security of Statist...

引用

28th International Workshop on Combinational algorithms (IWOCA)

作者： Kelarev, Andrei Seberry, Jennifer Rylands, Leanne Yi, Xun RMIT Univ Sch Sci GPO Box 2476 Melbourne Vic 3001 Australia Univ Wollongong Sch Comp & Informat Technol Northfields Ave Wollongong NSW 2522 Australia Western Sydney Univ Sch Comp Engn & Math Locked Bay 1797 Penrith NSW 2751 Australia

ISBN: (纸本)9783319788258;9783319788241

This article gives a survey of combinatorial algorithms and methods for database security related to the work of Mirka Miller. The main contributions of Mirka Miller and coauthors to the security of statistical databases include the introduction of Static Audit Expert and theorems determining time complexity of its combinatorial algorithms, a polynomial time algorithm for deciding whether the maximum possible usability can be achieved in statistical database with a special class of answerable statistics, NP-completeness of similar problems concerning several other types of databases, sharp upper bounds on the number of compromise-free queries in certain categories of statistical databases, and analogous results on applications of Static Audit Expert for the prevention of relative compromise.

关键词： combinatorial algorithms NP-completeness Privacy in data mining Database security Time complexity Sharp upper bounds

来源：评论

学校读者我要写书评

暂无评论

combinatorial algorithms for listing paths in minimal change order

引用

4th Workshop on combinatorial and Algorithmic Aspects of Networking

作者： Alamgir, Zareen Abbasi, Sarmad Natl Univ Comp & Emerging Sci Dept Comp Sci Block BFaisal Town Lahore Pakistan Lahore Univ Management Sci Ctr Adv Study Math Lahore Pakistan

ISBN: (纸本)9783540772934

combinatorial algorithms that list combinatorial objects in minimal change order are of fundamental interest in computer science and mathematics. In minimal change ordering, successive elements differ in some pre-specified small way. In this paper, we deal with the generation of paths in a special type of minimal change ordering, the revolving door ordering. We propose a simple algorithm to list all paths in a complete graph, K-n, with n vertices in revolving door order such that each path is generated exactly once. The algorithm is built using space and time efficient schemes that list all spanning paths and "path sets" in revolving door order. Our algorithm is optimal in the sense that it operates in constant amortized time (CAT) and uses linear space.

关键词： combinatorial algorithms minimal change order revolving door order complete graph generation of paths

来源：评论

学校读者我要写书评

暂无评论

PERFORMANCE EVALUATION OF VECTOR IMPLEMENTATIONS OF combinatorial algorithms

引用

PARALLEL COMPUTING 1984年第3-4期1卷 287-294页

作者： RIBEIRO, C Department of Electrical Engineering Catholic University of Rio de Janeiro Gavea-Caixa Postal 38063 Rio de Janeiro 22452 Brazil

We study the performance and the use of vector computers for the solution of combinatorial optimization problems, particularly dynamic programming and shortest path problems. A general model for performance evaluation and vector implementations for the problems described above are studied. These implementations were done on a CRAY-1 vector computer and the computational results obtained show (i) the adequacy of the performance evaluation model and (ii) very important gains concerning computing times, showing that vector computers will be of great importance in the field of combinatorial optimization.

关键词： CRAY-1 combinatorial algorithms vectorization performance analysis dynamic programming shortest path problems

来源：评论

学校读者我要写书评

暂无评论

Polynomial combinatorial algorithms for skew-bisubmodular function minimization

引用

MATHEMATICAL PROGRAMMING 2018年第1-2期171卷 87-114页

作者： Fujishige, Satoru Tanigawa, Shin-ichi Kyoto Univ Res Inst Math Sci Kyoto Japan Ctr Wiskunde & Informat Amsterdam Netherlands

Huber et al. (SIAM J Comput 43: 1064-1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28: 1828-1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12: 1-9, 2014) also showed a min-max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization.

关键词： Skew-bisubmodular functions Submodular functions Discrete convexity combinatorial algorithms Strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Opinion Optimization for Two Different Social Objectives: combinatorial algorithms and Linear Program Rounding

引用

Journal of Information Science and Engineering 2024年第2期40卷 217-230页

作者： Chen, Po-An Chen, Yi-Le Lo, Wei Institute of Information Management National Yang Ming Chiao Tung University Hsinchu City300 Taiwan

In this paper, we aim to optimize the two different social objectives of opinion optimization at equilibrium by controlling some individuals. This is usually called "Stackelberg games", in which a centralized authority is allowed to assign the strategies to a subset of individuals. The Stackelberg strategies of the centralized authority are the algorithms to select a subset of individuals and decide the actions for them in order to palliate the cost caused by the selfish behavior of the uncontrolled individuals. We give some combinatoral algorithms and linear program rounding algorithms as Stackelberg strategies for approximately optimizing the objective of utilitarian social cost (on special cases) and the objective of total expressed opinion (on general directed graphs), respectively. © 2024 Institute of Information Science. All rights reserved.

关键词： combinatorial algorithms linear program rounding opinion optimization randomized algorithms Stackelberg strategies

来源：评论

学校读者我要写书评

暂无评论

PROBABILISTIC ANALYSIS OF combinatorial algorithms - A BIBLIOGRAPHY WITH SELECTED ANNOTATIONS

引用

COMPUTING 1982年第3期28卷 257-267页

作者： SLOMINSKI, L Systems Research Institute Polish Academy of Sciences ul. Newelska 6 PL-01-447 Warszawa Poland

Probabilistic methods in evaluation of performance efficiency of combinatorial optimization algorithms are of continuously growing interest, and rapidly increasing effort of researchers in this field is observed. The present paper is a bibliography which contains 70 references dealing with probabilistic evaluation of time complexity and performance accuracy of deterministic algorithms for combinatorial decision and optimization problems. Some entries of the bibliography, mainly those having appreared in journals and nonperiodical issues of limited distribution are shortly annotated (18 references). Basic notions and definitions facilitating better understanding and plain presentation of different results are given.

关键词： combinatorial algorithms probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：