References of "Discrete Applied Mathematics"      in Complete repository Arts & humanities   Archaeology   Art & art history   Classical & oriental studies   History   Languages & linguistics   Literature   Performing arts   Philosophy & ethics   Religion & theology   Multidisciplinary, general & others Business & economic sciences   Accounting & auditing   Production, distribution & supply chain management   Finance   General management & organizational theory   Human resources management   Management information systems   Marketing   Strategy & innovation   Quantitative methods in economics & management   General economics & history of economic thought   International economics   Macroeconomics & monetary economics   Microeconomics   Economic systems & public economics   Social economics   Special economic topics (health, labor, transportation…)   Multidisciplinary, general & others Engineering, computing & technology   Aerospace & aeronautics engineering   Architecture   Chemical engineering   Civil engineering   Computer science   Electrical & electronics engineering   Energy   Geological, petroleum & mining engineering   Materials science & engineering   Mechanical engineering   Multidisciplinary, general & others Human health sciences   Alternative medicine   Anesthesia & intensive care   Cardiovascular & respiratory systems   Dentistry & oral medicine   Dermatology   Endocrinology, metabolism & nutrition   Forensic medicine   Gastroenterology & hepatology   General & internal medicine   Geriatrics   Hematology   Immunology & infectious disease   Laboratory medicine & medical technology   Neurology   Oncology   Ophthalmology   Orthopedics, rehabilitation & sports medicine   Otolaryngology   Pediatrics   Pharmacy, pharmacology & toxicology   Psychiatry   Public health, health care sciences & services   Radiology, nuclear medicine & imaging   Reproductive medicine (gynecology, andrology, obstetrics)   Rheumatology   Surgery   Urology & nephrology   Multidisciplinary, general & others Law, criminology & political science   Civil law   Criminal law & procedure   Criminology   Economic & commercial law   European & international law   Judicial law   Metalaw, Roman law, history of law & comparative law   Political science, public administration & international relations   Public law   Social law   Tax law   Multidisciplinary, general & others Life sciences   Agriculture & agronomy   Anatomy (cytology, histology, embryology...) & physiology   Animal production & animal husbandry   Aquatic sciences & oceanology   Biochemistry, biophysics & molecular biology   Biotechnology   Entomology & pest control   Environmental sciences & ecology   Food science   Genetics & genetic processes   Microbiology   Phytobiology (plant sciences, forestry, mycology...)   Veterinary medicine & animal health   Zoology   Multidisciplinary, general & others Physical, chemical, mathematical & earth Sciences   Chemistry   Earth sciences & physical geography   Mathematics   Physics   Space science, astronomy & astrophysics   Multidisciplinary, general & others Social & behavioral sciences, psychology   Animal psychology, ethology & psychobiology   Anthropology   Communication & mass media   Education & instruction   Human geography & demography   Library & information sciences   Neurosciences & behavior   Regional & inter-regional studies   Social work & social policy   Sociology & social sciences   Social, industrial & organizational psychology   Theoretical & cognitive psychology   Treatment & clinical psychology   Multidisciplinary, general & others     Showing results 1 to 9 of 9 1 Quadratization of symmetric pseudo-Boolean functionsAnthony, Martin; Boros, Endre; Crama, Yves et alin Discrete Applied Mathematics (2016), 203A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1 ... [more ▼]A pseudo-Boolean function is a real-valued function$f(x)=f(x_1,x_2,\ldots,x_n)$of$n$binary variables; that is, a mapping from$\{0,1\}^n$to${\bbr}$. For a pseudo-Boolean function$f(x)$on$\{0,1\}^n$, we say that$g(x,y)$is a quadratization of$f$if$g(x,y)$is a Quadratic polynomial depending on$x$and on$m$auxiliary binary variables$y_1,y_2,\ldots,y_m$such that$f(x)= \min \{ g(x,y) : y \in \{0,1\}^m \} $for all$x \in \{0,1\}^n$. By means of quadratizations, minimization of$f$is reduced to minimization (over its extended set of variables) of the quadratic function$g(x,y)$. This is of some practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and much progress has been made in solving such problems exactly or heuristically. A related paper initiated a systematic study of the minimum number of auxiliary$y$-variables required in a quadratization of an arbitrary function$f$(a natural question, since the complexity of minimizing the quadratic function$g(x,y)$depends, among other factors, on the number of binary variables). In this paper, we determine more precisely the number of auxiliary variables required by quadratizations of \emph{symmetric} pseudo-Boolean functions$f(x)$, those functions whose value depends only on the Hamming weight of the input$x\$ (the number of variables equal to 1). [less ▲]Detailed reference viewed: 85 (12 ULg) Influence and interaction indexes for pseudo-Boolean functions: a unified least squares approachMarichal, Jean-Luc; Mathonet, Pierre in Discrete Applied Mathematics (2014), 179The Banzhaf power and interaction indexes for a pseudo-Boolean function (or a cooperative game) appear naturally as leading coefficients in the stan- dard least squares approximation of the function by a ... [more ▼]The Banzhaf power and interaction indexes for a pseudo-Boolean function (or a cooperative game) appear naturally as leading coefficients in the stan- dard least squares approximation of the function by a pseudo-Boolean func- tion of a specified degree. We first observe that this property still holds if we consider approximations by pseudo-Boolean functions depending only on specified variables. We then show that the Banzhaf influence index can also be obtained from the latter approximation problem. Considering cer- tain weighted versions of this approximation problem, we introduce a class of weighted Banzhaf influence indexes, analyze their most important properties, and point out similarities between the weighted Banzhaf influence index and the corresponding weighted Banzhaf interaction index. We also discuss the issue of reconstructing a pseudo-Boolean function from prescribed influences and point out very different behaviors in the weighted and non-weighted cases. [less ▲]Detailed reference viewed: 13 (1 ULg) The interval ordering problemDurr, Christophe; Queyranne, Maurice; Spieksma, Frits C.R. et alin Discrete Applied Mathematics (2012)Detailed reference viewed: 12 (0 ULg) Approximations of Lovász extensions and their induced interaction indexMarichal, Jean-Luc; Mathonet, Pierre in Discrete Applied Mathematics (2008), 156(1), 11-24The Lovasz extension of a pseudo-Boolean function f : (0, 1)(n) -> R is defined on each simplex of the standard triangulation of [0, 1](n) as the unique affine function (f) over cap : [0, 1](n) -> R that ... [more ▼]The Lovasz extension of a pseudo-Boolean function f : (0, 1)(n) -> R is defined on each simplex of the standard triangulation of [0, 1](n) as the unique affine function (f) over cap : [0, 1](n) -> R that interpolates f at the n + 1 vertices of the simplex. Its degree is that of the unique multilinear polynomial that expresses f. In this paper we investigate the least squares approximation problem of an arbitrary Lovasz extension (f) over cap by Lovasz extensions of (at most) a specified degree. We derive explicit expressions of these approximations. The corresponding approximation problem for pseudo-Boolean functions was investigated by Hammer and Holzman [Approximations of pseudo-Boolean functions; applications to game theory, Z. Oper. Res. 36(1) (1992) 3-21] and then solved explicitly by Grabisch et al. [Equivalent representations of set functions, Math. Oper. Res. 25(2) (2000) 157-178], giving rise to an alternative definition of Banzhaf interaction index. Similarly we introduce a new interaction index from approximations of (f) over cap and we present some of its properties. It turns out that its corresponding power index identifies with the power index introduced by Grabisch and Labreuche [How to improve acts: an alternative representation of the importance of criteria in MCDM, Internat. J. Uncertain. Fuzziness Knowledge-Based Syst. 9(2) (2001) 145-157]. (c) 2007 Elsevier B.V. All rights reserved. [less ▲]Detailed reference viewed: 64 (10 ULg) Counting and enumerating aggregate classifiersAdem, Jan; Crama, Yves ; Gochet, Willy et alin Discrete Applied Mathematics (2008), 156(3), 2459-2468We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct ... [more ▼]We propose a generic model for the "weighted voting" aggregation step performed by several methods in supervised classification. Further, we construct an algorithm to count the number of distinct aggregate classifiers that arise in this model. When there are only two classes in the classification problem, we show that a class of functions that arises from aggregate classifiers coincides with the class of self-dual positive threshold Boolean functions. [less ▲]Detailed reference viewed: 48 (14 ULg) Consensus algorithms for the generation of all maximal bicliquesAlexe, Gabriela; Alexe, Sorin; Crama, Yves et alin Discrete Applied Mathematics (2004), 145(1 Sp. Iss. SI), 11-21We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite. not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to. the ... [more ▼]We describe a new algorithm for generating all maximal bicliques (i.e. complete bipartite. not necessarily induced subgraphs) of a graph. The algorithm is inspired by, and is quite similar to. the consensus method used in propositional logic. We show that some variants of the algorithm are totally polynomial, and even incrementally polynomial. The total complexity of the most efficient variant of the algorithms presented here is polynomial in the input size. and only linear in the output size. Computational experiments demonstrate its high efficiency on randomly generated graphs with up to 2000 vertices and 20,000 edges. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]Detailed reference viewed: 88 (6 ULg) The maximum deviation just-in-time scheduling problemBrauner, Nadia; Crama, Yves in Discrete Applied Mathematics (2004), 134(1-3), 25-50This note revisits the maximum deviation just-in-time (MDJIT) scheduling problem previously investigated by Steiner and Yeomans. Its main result is a set of algebraic necessary and sufficient conditions ... [more ▼]This note revisits the maximum deviation just-in-time (MDJIT) scheduling problem previously investigated by Steiner and Yeomans. Its main result is a set of algebraic necessary and sufficient conditions for the existence of a MDJIT schedule with a given objective function value. These conditions are used to provide a finer analysis of the complexity of the MDJIT problem. The note also investigates various special cases of the MDJIT problem and suggests several questions for further investigation. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]Detailed reference viewed: 181 (5 ULg) The commutative closure of a binary slip-language is context-free: a new proofRigo, Michel in Discrete Applied Mathematics (2003), 131(3), 665-672Using original arguments about sets of integers satisfying some first-order formula of the Presburger arithmetic , we give a new proof that the commutative closure of a slip-language over a two ... [more ▼]Using original arguments about sets of integers satisfying some first-order formula of the Presburger arithmetic , we give a new proof that the commutative closure of a slip-language over a two letters alphabet is context-free. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]Detailed reference viewed: 19 (4 ULg) Production planning problems in printed circuit board assemblyCrama, Yves ; van de Klundert, Joris; Spieksma, Frits CRin Discrete Applied Mathematics (2002), 123(1-3), 339-361This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical ... [more ▼]This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical decomposition of the planning process into distinct optimization subproblems, addressing issues such as the assignment of board types to machine groups, the allocation of component feeders to individual machines, the determination of optimal production sequences, etc, The paper reviews the literature on this topic with an emphasis on the most recent developments, on the fundamental structure of the mathematical models and on the relation between these models and some 'environmental' variables such as the layout of the shop or the product mix. (C) 2002 Elsevier Science B.V, All rights reserved. [less ▲]Detailed reference viewed: 358 (7 ULg) 1