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

CHVATAL CUTS AND ODD CYCLE INEQUALITIES IN QUADRATIC 0 - 1 OPTIMIZATION

SIAM JOURNAL ON DISCRETE MATHEMATICS 1992年第2期5卷 163-177页

作者： BOROS, E CRAMA, Y HAMMER, PL RUTGERS STATE UNIV RUTCORNEW BRUNSWICKNJ 08903 UNIV LIMBURG DEPT QUANTITAT ECON6200 MD MAASTRICHTNETHERLANDS

In this paper a new lower bound for unconstrained quadratic 0-1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the number of variables;and it is shown that the polyhedron S[3], defined by the constraints of this LP formulation is precisely the first Chvatal closure of the polyhedron associated with standard linearization procedures. By rewriting the quadratic minimization problem as a balancing problem in a weighted signed graph, it can be seen that the polyhedron defined by the odd cycle inequalities is equivalent, in a certain sense, with S[3]. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs.

关键词： UNCONSTRAINED QUADRATIC 0 - 1 PROGRAMMING pseudo-boolean functions WEIGHTED 2-SATISFIABILITY MAXIMUM CUT PROBLEM CHVATAL CUT CHVATAL CLOSURE

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Approximating the Distribution of Fitness over Hamming Regions 11

Approximating the Distribution of Fitness over Hamming Regio...

引用

11th Foundations of Genetic Algorithms Workshop

作者： Sutton, Andrew M. Whitley, L. Darrell Howe, Adele E. Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA

ISBN: (纸本)9781450306331

The distribution of fitness values across a set of states sharply influences the dynamics of evolutionary processes and heuristic search in combinatorial optimization. In this paper we present a method for approximating the distribution of fitness values over Hamming regions by solving a linear programming problem that incorporates low order moments of the target function. These moments can be retrieved in polynomial time for select problems such as MAX-k-SAT using Walsh analysis. The method is applicable to any real function on binary strings that is epistatically bounded and discrete with asymptotic bounds on the cardinality of its codomain. We perform several studies on the ONE-MAX and MAX-k-SAT domains to assess the accuracy of the approximation and its dependence on various factors. We show that the approximation can accurately predict the number of states within a Hamming region that have an improving fitness value.

关键词： pseudo-boolean functions search space analysis

来源：评论

学校读者我要写书评

暂无评论

Stochastic Side-Channel Leakage Analysis via Orthonormal Decomposition 1

引用

10th International Conference on Security for Information Technology and Communications (SECITC)

作者： Guilley, Sylvain Heuser, Annelie Ming, Tang Rioul, Olivier Secure IC SAS Cesson Sevigne France Univ Paris Saclay LTCI Telecom ParisTech Paris France CNRS IRISA Rennes France Wuhan Univ Wuhan Peoples R China

ISBN: (数字)9783319692845

ISBN: (纸本)9783319692845;9783319692838

Side-channel attacks of maximal efficiency require an accurate knowledge of the leakage function. Template attacks have been introduced by Chari et al. at CHES 2002 to estimate the leakage function using available training data. Schindler et al. noticed at CHES 2005 that the complexity of profiling could be alleviated if the evaluator has some prior knowledge on the leakage function. The initial idea of Schindler is that an engineer can model the leakage from the structure of the circuit. However, for some thin CMOS technologies or some advanced countermeasures, the engineer intuition might not be sufficient. Therefore, inferring the leakage function based on profiling is still important. In the state-of-the-art, though, the profiling stage is conducted based on a linear regression in a non-orthonormal basis. This does not allow for an easy interpretation because the components are not independent. In this paper, we present a method to characterize the leakage based on a Walsh-Hadamard orthonormal basis with staggered degrees, which allows for direct interpretations in terms of bits interactions. A straightforward application is the characterization of a class of devices in order to understand their leakage structure. Such information is precious for designers and also for evaluators, who can devise attack bases relevantly.

关键词： Side-channel analysis Stochastic attacks Leakage model pseudo-boolean functions Orthonormal bases Leakage characterization

来源：评论

学校读者我要写书评

暂无评论

Do Additional Optima Speed Up Evolutionary Algorithms? 21

Do Additional Optima Speed Up Evolutionary Algorithms?

引用

16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA)

作者： Bossek, Jakob Sudholt, Dirk Univ Munster Dept Informat Syst Munster Germany Univ Passau Dept Comp Sci & Math Passau Germany

ISBN: (纸本)9781450383523

Most runtime analyses of randomised search heuristics focus on the expected number of function evaluations to find a unique global optimum. We ask a fundamental question: if additional search points are declared optimal, or declared as desirable target points, do these additional optima speed up evolutionary algorithms? More formally, we analyse the expected hitting time of a target set OPT u S where S is a set of non-optimal search points and OPT is the set of optima and compare it to the expected hitting time of OPT. We show that the answer to our question depends on the number and placement of search points in S. For all black-box algorithms and all fitness functions we show that, if additional optima are placed randomly, even an exponential number of optima has a negligible effect on the expected optimisation time. Considering Hamming balls around all global optima gives an easier target for some algorithms and functions and can shift the phase transition with respect to offspring population sizes in the (1,lambda) EA on ONE-MAX. Finally, on functions where search trajectories typically join in a single search point, turning one search point into an optimum drastically reduces the expected optimisation time.

关键词： Evolutionary algorithms pseudo-boolean functions runtime analysis theory

来源：评论

学校读者我要写书评

暂无评论

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

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

来源：评论

学校读者我要写书评

暂无评论

Higher-Order Clique Reduction Without Auxiliary Variables 27

Higher-Order Clique Reduction Without Auxiliary Variables

引用

27th IEEE Conference on Computer Vision and Pattern Recognition (CVPR)

作者： Ishikawa, Hiroshi Waseda Univ Dept Comp Sci & Engn Shinjuku Ku Tokyo Japan

ISBN: (纸本)9781479951178

We introduce a method to reduce most higher-order terms of Markov Random Fields with binary labels into lower-order ones without introducing any new variables, while keeping the minimizer of the energy unchanged. While the method does not reduce all terms, it can be used with existing techniques that transforms arbitrary terms (by introducing auxiliary variables) and improve the speed. The method eliminates a higher-order term in the polynomial representation of the energy by finding the value assignment to the variables involved that cannot be part of a global minimizer and increasing the potential value only when that particular combination occurs by the exact amount that makes the potential of lower order. We also introduce a faster approximation that forego the guarantee of exact equivalence of minimizer in favor of speed. With experiments on the same field of experts dataset used in previous work, we show that the roof-dual algorithm after the reduction labels significantly more variables and the energy converges more rapidly.

关键词： Graph cuts Higher order Order reduction pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Understanding the Cost of Fitness Evaluation for Subset Selection: Markov Chain Analysis of Stochastic Local Search

Understanding the Cost of Fitness Evaluation for Subset Sele...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Mengshoel, Ole Jakob Flogard, Eirik Lund Yu, Tong Riege, Jon Norwegian Univ Sci & Technol Trondheim Norway Norwegian Labour Inspect Author Trondheim Norway Carnegie Mellon Univ Pittsburgh PA 15213 USA Boston Consulting Grp Inc Oslo Norway

ISBN: (纸本)9781450392372

With a focus on both the fitness and cost of subset selection, we study stochastic local search (SLS) heuristics in this paper. In particular, we consider subset selection problems where the cost of fitness function evaluation needs to be accounted for. Here, cost can be fitness evaluation's computation time or energy cost. We propose and study an SLS method, SLS4CFF, tailored to such problems. SLS4CFF ("SLS for costly fitness functions") is an amalgamation of several existing heuristics. We develop a homogeneous Markov chain model that explicitly represents both fitness and cost of subset selection with SLS4CFF. This Markov chain, which can be lumped or compressed for certain fitness and cost functions, enables us to better understand and analyze hyperparameter optimization in a principled manner, via expected hitting times. Studies with synthetic and real-world problems improve the understanding of SLS and demonstrate the importance of cost-awareness.

关键词： pseudo-boolean functions costly fitness functions synthetic problems optimization stochastic local search Markov chain analysis expected hitting time machine learning classification

来源：评论

学校读者我要写书评

暂无评论

Simultaneously Satisfying Linear Equations Over F₂: MaxLin2 and Max-r-Lin2 Parameterized Above Averag

Simultaneously Satisfying Linear Equations Over F<sub>2</sub...

引用

31st IARCS Annual International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

作者： Crowston, Robert Fellows, Michael Gutin, Gregory Jones, Mark Rosamond, Frances Thomasse, Stephan Yeo, Anders Univ London Egham TW20 0EX Surrey England Charles Darwin Univ Darwin NT 0909 Australia Univ Montpellier 2 LIRMM F-34392 Montpellier France

ISBN: (纸本)9783939897347

In the parameterized problem MaxLin2-AA[k], we are given a system with variables x1,..., xn consisting of equations of the form Pi(i epsilon I) x(i) = b, where x(i), b epsilon {-1, 1} and I subset of [n], each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2 + k, where W is the total weight of all equations and k is the parameter (if k = 0, the possibility is assured). We show that MaxLin2-AA[k] has a kernel with at most O(k(2) log k) variables and can be solved in time 2(O(k log k)) (nm)(O(1)). This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k, r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove a theorem on Max-r-Lin2-AA[k, r] which implies that Max-r-Lin2-AA[k, r] has a kernel with at most (2k -1) r variables, improving a number of results including one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a function f : {-1, 1}(n) -> R whose Fourier expansion (which is a multilinear polynomial) is of degree r. We show applicability of the lower bound by giving a new proof of the Edwards-Erdos bound (each connected graph on n vertices and m edges has a bipartite subgraph with at least m/2+(n-1)/4 edges) and obtaining a generalization.

关键词： MaxLin fixed-parameter tractability kernelization pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Testing optimality for quadratic 0-1 unconstrained problems

引用

ZOR Zeitschrift für Operations Research Mathematical Methods of Operations Research 1995年第3期42卷 295-311页

作者： Carraresi, Paolo Malucelli, Federico Pappalardo, Massimo Dipartimento di Informatica Universita di Pisa Pisa 56125 Corso Italia 40 Italy Dipartimento di Matematica Universita di Pisa Pisa 56127 Via Buonarroti 2 Italy

This paper analyses a necessary and sufficient optimality condition for quadratic pseudo-boolean unconstrained problems. It is proved that in general testing any necessary and sufficient optimality condition is a difficult task for any NP-hard problem. An e{open}-optimality condition is derived together with an approximation scheme to test it. © 1995 Physica-Verlag.

关键词： Combinatorial Optimisation Convex Analysis e{open}-normal directions e{open}-subgradient pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：