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

Generalizations of Swierczkowski's lemma and the arity gap of finite functions

DISCRETE MATHEMATICS 2009年第20期309卷 5905-5912页

作者： Couceiro, Miguel Lehtonen, Erkko Univ Luxembourg Dept Math L-1511 Luxembourg Luxembourg Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Tampere Univ Technol Dept Math FI-33101 Tampere Finland

Swierczkowski's lemma - as it is usually formulated - asserts that if f . A(n) -> A is an operation on a finite set A, n >= 4, and every operation obtained from f by identifying a pair of variables is a projection. then f is a semiprojection We generalize this lemma in various ways. First. it is extended to B-valued functions on A instead of operations oil A and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Swierczkowski's lemma. Moreover, we explicitly classify all pseudo-boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of B-valued functions oil arbitrary finite sets A (C) 2009 Elsevier E.V. All rights reserved.

关键词： Finite functions boolean functions pseudo-boolean functions Variable substitution Variable identification minors Essential variables Arity gap Semiprojection

来源：评论

学校读者我要写书评

暂无评论

Submodularity, supermodularity, and higher-order monotonicities of pseudo-boolean functions

引用

MATHEMATICS OF OPERATIONS RESEARCH 2005年第2期30卷 453-461页

作者： Foldes, S Hammer, PL Tampere Univ Technol Inst Math Miami FL 33101 USA Rutgers State Univ Rutgers Ctr Operat Res RUTCOR Piscataway NJ 08854 USA

Classes of set functions defined by the positivity or negativity of the higher-order derivatives of their pseudo-boolean polynomial representations generalize those of monotone, supermodular, and submodular functions. In this paper, these classes are characterized by functional inequalities and are shown to be closed both under algebraic closure conditions and a local closure criterion. It is shown that for every m : 1, in addition to the class of all set functions, there are only three other classes satisfying these algebraic and local closure conditions: those having positive, respectively negative, mth-order derivatives, and those having a polynomial representation of degree less than m.

关键词： set functions boolean functions pseudo-boolean functions submodularity supermodularity discrete derivatives Post classes functional inequalities functional equations minors local closure

来源：评论

学校读者我要写书评

暂无评论

Complexity of local search for the p-median problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第3期191卷 736-752页

作者： Alekseeva, Ekaterina Kochetov, Yuri Plyasunov, Alexander Sobolev Inst Math Novosibirsk Russia

We study the complexity of finding local minima for the p-median problem. The relationship between Swap local optima, 0-1 local saddle points, and classical Karush-Kuhn-Tucker conditions is presented. It is shown that the local search problems with some neighborhoods are tight PLS-complete. Moreover, the standard local descent algorithm takes exponential number of iterations in the worst case regardless of the tie-breaking and pivoting rules used. To illustrate this property, we present a family of instances where some local minima may be hard to find. Computational results with different pivoting rules for random and Euclidean test instances are discussed. These empirical results show that the standard local descent algorithm is polynomial in average for some pivoting rules. (C) 2007 Elsevier B.V. All rights reserved.

关键词： local search PLS-completeness pivoting rules Karush-Kuhn-Tucker conditions 0-1 local saddle points pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT REDUCTION OF POLYNOMIAL ZERO-ONE OPTIMIZATION TO THE QUADRATIC CASE

引用

SIAM JOURNAL ON OPTIMIZATION 2008年第4期18卷 1398-1413页

作者： Buchheim, Christoph Rinaldi, Giovanni Univ Cologne Inst Informat D-50969 Cologne Germany CNR Ist Anal Sistemi Informat Antonio Ruberti I-00185 Rome Italy

We address the problem of optimizing a polynomial with real coefficients over binary variables. We show that a complete polyhedral description of the linearization of such a problem can be derived in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation does not contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows us to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. We report preliminary experimental results obtained with a straightforward implementation of this approach.

关键词： polynomial zero-one optimization integer nonlinear programming pseudo-boolean functions max-cut problem multilinear function optimization

来源：评论

学校读者我要写书评

暂无评论

FPGA implementation of a stochastic neural network for monotonic pseudo-boolean optimization

引用

NEURAL NETWORKS 2008年第6期21卷 872-879页

作者： Grossi, Giuliano Pedersini, Federico Univ Milan Dipartimento Sci Informaz I-20135 Milan Italy

In this paper a FPGA implementation of a novel neural stochastic model for solving constrained NP-hard problems is proposed and developed. The model exploits pseudo-boolean functions both to express the constraints and to define the cost function, interpreted as energy of a neural network. A wide variety of NP-hard problems falls in the class of problems that can be solved by this model, particularly those having a quadratic pseudo-boolean penalty function. The proposed hardware implementation provides high computation speed by exploiting parallelism, as the neuron update and the constraint violation check can be performed in parallel over the whole network. The neural system has been tested on random and benchmark graphs, showing good performance with respect to the same heuristic for the same problems. Furthermore, the computational speed of the FPGA implementation has been measured and compared to software implementation. The developed architecture featured dramatically faster computation, with respect to the software implementation, even adopting a low-cost FPGA chip. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： stochastic model FPGA optimization pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Disjunctive analogues of submodular and supermodular pseudo-boolean functions

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期142卷 53-65页

作者： Foldes, S Hammer, PL Tampere Univ Technol Dept Math FIN-33101 Tampere Finland Rutgers State Univ RUTCOR Piscataway NJ 08854 USA

We consider classes of real-valued functions of boolean variables defined by disjunctive analogues of the submodular and supermodular functional inequalities, obtained by replacing in these inequalities addition by disjunction (max operator). The disjunctive analogues of submodular and supermodular functions are completely characterized by the syntax of their disjunctive normal forms. Classes of functions possessing combinations of these properties are also examined. A disjunctive representation theory based on one of these combination classes exhibits syntactic and algorithmic analogies with classical DNF theory. (C) 2003 Published by Elsevier B.V.

关键词： submodularity supermodularity pseudo-boolean functions disjunctive normal form implicents conseusus resolution

来源：评论

学校读者我要写书评

暂无评论

Functional Equations, Constraints, Definability of Function Classes, and functions of boolean Variables

引用

ACTA CYBERNETICA 2007年第1期18卷 61-75页

作者： Couceiro, Miguel Foldes, Stephan Univ Tampere Dept Math Stat & Philosophy Kansleririnne 1 Tampere 33014 Finland Tampere Univ Technol PL553 Inst Math FIN-33101 Tampere Finland

The paper deals with classes of functions of several variables defined on an arbitrary set A and taking values in a possibly different set B. Definability of function classes by functional equations is shown to be equivalent to definability by relational constraints, generalizing a fact established by Pippenger in the case A = B = {0,1}. Conditions for a class of functions to be definable by constraints of a particular type are given in terms of stability under certain functional compositions. This leads to a correspondence between functional equations with particular algebraic syntax and relational constraints with certain invariance properties with respect to clones of operations on a given set. When A = {0, 1} and B is a commutative ring, such B-valued functions of n variables are represented by multilinear polynomials in n indeterminates in B[X-1,...,X-n]. Functional equations are given to describe classes of field-valued functions of a specified bounded degree. Classes of boolean and pseudo-boolean functions are covered as particular cases.

关键词： Function classes class composition stability functional equations relational constraints function class definability ring-valued functions multilinear polynomial representations linear equations field-valued functions of boolean variables boolean functions pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Exact and heuristic approaches to input vector control for leakage power reduction

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2006年第11期25卷 2564-2571页

作者： Gao, Feng Hayes, John P. Adv Micro Devices Inc Boxboro MA 01719 USA Univ Michigan Adv Comp Architecture Lab Ann Arbor MI 48109 USA

Leakage power consumption is an increasingly serious problem in very large-scale integration circuits, especially for portable applications. Two novel approaches to leakage power minimization in static complementary metal-oxide-semiconductor circuits that employ input vector control (IVC) are investigated. The authors model leakage effects by means of pseudo-boolean functions. These functions are linearized and incorporated into an exact (optimal) integer linear programming (ILP) model, called virtual-gate ILP, which analyzes leakage variation with respect to a circuit's input vectors. A heuristic mixed-integer linear programming (MLP) method is also proposed, which has several advantages: it is faster, its accuracy can be quickly estimated, and tradeoffs between runtime and optimality can easily be made. Furthermore, the MLP model also provides a way to estimate a lower bound on circuit leakage current. The proposed methods are used to generate an extensive set of experimental results on leakage reduction. It is shown that average leakage currents are usually 1.25 times the minimum, confirming the effectiveness of IVC. The heuristic MLP approach is shown to be approximately 13.6 times faster than the exact ILP method, whereas finding input vectors whose power consumption is only a few percent above the optimum. In addition, the lower bound estimated by the MLP model is also within a few percent of the optimal value.

关键词： input vector control integer linear programming leakage current minimization pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Optimal testing and repairing a failed series system

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2006年第3期12卷 279-295页

作者： Kovalyov, Mikhail Y. Portmann, Marie-Claude Oulamara, Ammar Ecole Mines Nancy MACSI Project LORIA INRIA F-540042 Nancy France Natl Acad Sci Belarus United Inst Informat Problems Minsk 220050 BELARUS Belarusian State Univ Fac Econ F-540042 Nancy France

We consider a series repairable system that includes n components and assume that it has just failed because exactly one of its components has failed. The failed component is unknown. Probability of each component to be responsible for the failure is given. Each component can be tested and repaired at given costs. Both testing and repairing operations are assumed to be perfect, that is, the result of testing a component is a true information that this component is failed or active (not failed), and the result of repairing is that the component becomes active. The problem is to find a sequence of testing and repairing operations over the components such that the system is always repaired and the total expected cost of testing and repairing the components is minimized. We show that this problem is equivalent to minimizing a quadratic pseudo-boolean function. Polynomially solvable special cases of the latter problem are identified and a fully polynomial time approximation scheme (FPTAS) is derived for the general case. Computer experiments are provided to demonstrate high efficiency of the proposed FPTAS. In particular, it is able to find a solution with relative error epsilon = 0.1 for problems with more than 4000 components within 5 minutes on a standard PC with 1.2 Mhz processor.

关键词： test and repair policies failure diagnosis optimization pseudo-boolean functions fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Exact and heuristic approaches to input vector control for leakage power reduction 04

Exact and heuristic approaches to input vector control for l...

引用

International Conference on Computer Aided Design (ICCAD 2004)

作者： Gao, Feng Hayes, John P. Adv Micro Devices Inc Boxboro MA 01719 USA Univ Michigan Adv Comp Architecture Lab Ann Arbor MI 48109 USA

ISBN: (纸本)9780780387027

关键词： input vector control integer linear programming leakage current minimization pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：