Search

Given a simple undirected graph G and a positive integer s, the maximum vertex coverage problem (MVC) is the problem of finding a set U of s vertices of G such that the number of edges having at least one endpoint in U is as large as possible. The problem is NP-hard even in bipartite graphs, as shown in two recent papers [N. Apollonio and B. Simeone, Discrete Appl. Math., 165 (2014), pp. 37-48; G. Joret and A. Vetta, Reducing the Rank of a Matroid, preprint, arXiv:1211.4853v1 [cs.DS], 2012]. By exploiting the structure of the fractional optimal solutions of a linear programming formulation for the maximum coverage problem, we provide a 4/5-approximation algorithm for the problem. The algorithm immediately extends to the weighted version of MVC. [ABSTRACT FROM AUTHOR]

Abstract: Given a simple undirected graph and a positive integer the Maximum Vertex Coverage Problem is the problem of finding a set of vertices of such that the number of edges having at least one endpoint in is as large as possible. We prove that the Maximum Vertex Coverage problem on bipartite graphs is NP-hard and discuss several consequences related to known combinatorial optimization problems. [Copyright &y& Elsevier]

The biproportional apportionment problem (BAP) must be faced in many proportional electoral systems where seats must be allocated to parties within regions. BAP is a non-trivial optimization problem, and only sophisticated algorithms are currently available for solving it. The issue is: are they 'writable' as an actual law? Citizens rightly demand simple, easy to understand, voting systems. The alternative, though, seems to have simple, but unsound electoral laws. We propose the following way out of this dilemma: leave to a mathematically sophisticated algorithm the task of producing an optimal apportionment, but attach to it a 'certificate of optimality', that is, describe a simple procedure whereby anybody can check, through some elementary operations, that the seat allocation output by the algorithm is indeed an optimal apportionment. We discuss one such certificate, based on the Max flow- min cut Theorem, relative to a parametric max flow method of ours for BAP. [ABSTRACT FROM AUTHOR]

Abstract: It is proved that any pseudo-Boolean function can be represented as , where z is the minimum of and is a polynomial with positive coefficients in the original variables and in their complements . A non-constructive proof and a constructive one are given. The latter, which is based on a generalization to pseudo-Boolean functions of the well-known Boolean-theoretical operation of consensus, provides a new algorithm for the minimization of pseudo-Boolean functions. [Copyright &y& Elsevier]

This paper is devoted to a new problem of combinatorial optimization. The problem is called Maximum Weight Archipelago Subgraph Problem (MWASP). Archipelago is a signed graph such that the negative edges connect the components of the graph of the positive edges. The new problem is to find a subset of edges in a weighted signed graph such that (i) if the edges of the subset are deleted from the graph then the remaining graph is an archipelago; and (ii) the subset has minimal total weight among the subsets having property (i). The problem is NP-complete, however a polynomial algorithm is provided to obtain the maximal weight of an edge what is still necessary to delete. The problem MWAP is used to analyze the relation of the blue chips of the Dow Jones Index. [ABSTRACT FROM AUTHOR]

The Political Districting problem has been studied since the 60's and many different models and techniques have been proposed with the aim of preventing districts' manipulation which may favor some specific political party ( gerrymandering). A variety of Political Districting models and procedures was provided in the Operations Research literature, based on single- or multiple-objective optimization. Starting from the forerunning papers published in the 60's, this article reviews some selected optimization models and algorithms for Political Districting which gave rise to the main lines of research on this topic in the Operations Research literature of the last five decades. [ABSTRACT FROM AUTHOR]

Abstract: The current electoral law for the Italian Parliament prescribes blocked, linearly ordered lists of candidates for each party within each constituency. The peculiarity of the Italian electoral system is that a party can present the same candidate in different constituencies. There are several seats at stake in each constituency; these seats are allocated to the parties proportionally to the total number of votes they get. If the blocked list mechanism–which assigns the seats obtained by a party in a constituency to the first candidates of the corresponding ordered list–causes some candidates to win in more than one constituency, they may retain only one of the seats, giving up all the remaining ones. Thus, the problem arises for a party to find a suitable “schedule of give-ups” that produces the final set of winners for that party. In order to do this, we assume that such decision is centralized and based on some models of global (inter-regional) preferences over the set of candidates. In this paper, we introduce two classes of models to formulate the “give-up problem”, i.e., utility and ordinal models, and we show that for both of them some natural formulations of the problem can be efficiently solved by network flows techniques. [Copyright &y& Elsevier]

Abstract: Clustering problems with relational constraints in which the underlying graph is a tree arise in a variety of applications: hierarchical data base paging, communication and distribution networks, districting, biological taxonomy, and others. They are formulated here as optimal tree partitioning problems. In a previous paper, it was shown that their computational complexity strongly depends on the nature of the objective function and, in particular, that minimizing the total within-cluster dissimilarity or the diameter is computationally hard. We propose heuristics that find good partitions within a reasonable time, even for instances of relatively large size. Such heuristics are based on the solution of continuous relaxations of certain integer (or almost integer) linear programs. Experimental results on over 2000 randomly generated instances with up to 500 entities show that the values (total within-cluster dissimilarity or diameter) of the solutions provided by these heuristics are quite close to the minimum one. [Copyright &y& Elsevier]

Abstract: Political districting on a given territory can be modelled as bi-objective partitioning of a graph into connected components. The nodes of the graph represent territorial units and are weighted by populations; edges represent pairs of geographically contiguous units and are weighted by road distances between the two units. When a majority voting rule is adopted, two reasonable objectives are population equality and compactness. The ensuing combinatorial optimization problem is extremely hard to solve exactly, even when only the single objective of population equality is considered. Therefore, it makes sense to use heuristics. We propose a new class of them, based on discrete weighted Voronoi regions, for obtaining compact and balanced districts, and discuss some formal properties of these algorithms. These algorithms feature an iterative updating of the distances in order to balance district populations as much as possible. Their performance has been tested on randomly generated rectangular grids, as well as on real-life benchmarks; for the latter instances the resulting district maps are compared with the institutional ones adopted in the Italian political elections from 1994 to 2001. [Copyright &y& Elsevier]

A usual technique to generate upper bounds on the optimum of a quadratic 0–1 maximization problem is to consider a linear majorant (LM) of the quadratic objective function f and then solve the corresponding linear relaxation. Several papers have considered LMs obtained by termwise bounding, but the possibility of bounding groups of terms simultaneously does not appear to have been given much attention so far. In the present paper a broad and flexible computational framework is developed for implementing such a strategy. Here is a brief overview of our approach: in the first place, a suitable collection of “elementary” quadratic functions of few variables (typically, 3 or 4) is generated. All the coefficients of any such function (block) are either 1 or -1, and agree in sign with the corresponding coefficients of the given quadratic function. Next, for each block, a tightest LM (i.e., one having the same value as the block in as many points as possible), or a closest LM (i.e., one minimizing the sum of slacks) is computed. This can be accomplished through the solution of a small mixed-integer program, or a small linear program, respectively. Finally, the objective function is written as a weighted sum of blocks, with non-negative weights. Replacing in this expression each block by the corresponding LM yields an LM of f. We shall choose the weights in this process so that the maximum value of the resulting linear function is as small as possible. This amounts to a large-scale (but still polynomial-size) linear program, which may be solved exactly or, for larger instances, approximately by truncated column generation. The results of a set of 480 numerical tests with up to 200 variables are presented: the upper bounds on the quadratic optimum obtained by the above procedure are (provably) never worse, and often turn out to be substantially sharper, than those resulting from termwise bounding. Moreover, our bounds turn out to be close to the optimum in many (although not all) instances of some well-known benchmarks. [Copyright &y& Elsevier]

Abstract: Patterns are the key building blocks in the logical analysis of data (LAD). It has been observed in empirical studies and practical applications that some patterns are more “suitable” than others for use in LAD. In this paper, we model various such suitability criteria as partial preorders defined on the set of patterns. We introduce three such preferences, and describe patterns which are Pareto-optimal with respect to any one of them, or to certain combinations of them. We develop polynomial time algorithms for recognizing Pareto-optimal patterns, as well as for transforming an arbitrary pattern to a better Pareto-optimal one with respect to any one of the considered criteria, or their combinations. We obtain analytical representations characterizing some of the sets of Pareto-optimal patterns, and investigate the computational complexity of generating all Pareto-optimal patterns. The empirical evaluation of the relative merits of various types of Pareto-optimality is carried out by comparing the classification accuracy of Pareto-optimal theories on several real life data sets. This evaluation indicates the advantages of “strong patterns”, i.e. those patterns which are Pareto-optimal with respect to the “evidential preference” introduced in this paper. [Copyright &y& Elsevier]

Clique partitioning in Euclidean space Rn consists in finding a partition of a given set of N points into M clusters in order to minimize the sum of within-cluster interpoint distances. For n=1 clusters need not consist of consecutive points on a line but have a nestedness property. Exploiting this property, an O(N5M2) dynamic programming algorithm is proposed. A θ(N) algorithm is also given for the case M=2. [Copyright &y& Elsevier]

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. [Copyright &y& Elsevier]

Consider N entities to be classified (e.g., geographical areas), a matrix of dissimilarities between pairs of entities, a graph H with vertices associated with these entities such that the edges join the vertices corresponding to contiguous entities. The split of a cluster is the smallest dissimilarity between an entity of this cluster and an entity outside of it. The single-linkage algorithm (ignoring contiguity between entities) provides partitions into M clusters for which the smallest split of the clusters, called split of the partition, is maximum. We study here the partitioning of the set of entities into M connected clusters for all M between N - 1 and 2 (i.e., clusters such that the subgraphs of H induced by their corresponding sets of entities are connected) with maximum split subject to that condition. We first provide an exact algorithm with a Θ(N²) complexity for the particular case in which H is a tree. This algorithm suggests in turn a first heuristic algorithm for the general problem. Several variants of this heuristic are also explored. We then present an exact algorithm for the general case based on iterative determination of cocycles of subtrees and on the solution of auxiliary set covering problems. As solution of the latter problems is time-consuming for large instances, we provide another heuristic in which the auxiliary set covering problems are solved approximately. Computational results obtained with the exact and heuristic algorithms are presented on test problems from the literature. [ABSTRACT FROM AUTHOR]