In this paper, we study the Perfect Awareness Problem (PAP), which models the spreading of information on social networks. In this problem, we seek to find a smallest subset of seminal individuals that are sufficient to ascertain that a given news reaches everyone on a network, under certain dissemination restrictions. Knowing that PAP is NP-hard, we present three novel heuristics based on the metaheuristic GRASP and show that the best of our methods outperforms the only previously known heuristic. Besides the actual heuristics, our contributions include a new publicly available benchmark of 840 instances that simulate social network relations, approaches for preprocessing instances, and a linear programming formulation to generate exact solutions for PAP. Lastly, we present an exhaustive set of comparative experiments, followed by statistical analyses, showing the efficacy and efficiency of our algorithms.

In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions use Integer Linear Programming (ILP) modeling and rely on state-of-the- art solvers to be able to find optimal solutions for large instances in a matter of minutes. In this work, we discuss an ILP-based algorithm that solves to optimality the Art Gallery Problem (AGP), one of the most studied problems in computational geometry. The basic idea of our method is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. Our algorithm was implemented and tested on almost 3,000 instances and attained optimal solutions for the vast majority of them, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively and efficiently as the one described here. Evidence of its robustness is presented through tests done on a number of classes of polygons of various sizes with and without holes. A software package implementing the algorithm is made available.

Proportional symbol maps are a cartographic tool to assist in the visualization and analysis of quantitative data associated with specific locations, such as earthquake magnitudes, oil well production, and temperature at weather stations. As the name suggests, symbol sizes are proportional to the magnitude of the physical quantities that they represent. We present two novel integer linear programming (ILP) models to solve this computational geometry problem: how to draw opaque disks on a map so as to maximize the total visible border of all disks. We focus on drawings obtained by layering symbols on top of each other, also known as stacking drawings. We introduce decomposition techniques as well as several families of facet-defining inequalities, which are used to strengthen the ILP models that are supplied to a commercial solver. We demonstrate the effectiveness of our approach through a series of computational experiments using hundreds of instances generated from real demographic and geophysical data sets. To the best of our knowledge, we are the first to use ILP to tackle this problem, and the first to provide provably optimal symbol maps for those data sets.

In this video, we illustrate how one of the classical areas of computational geometry has gained in practical relevance, which in turn gives rise to new, fascinating geometric problems. In particular, we demonstrate how the robot platform IRMA3D can produce high-resolution, virtual 3D environments, based on a limited number of laser scans. Computing an optimal set of scans amounts to solving an instance of the Art Gallery Problem (AGP): Place a minimum number of stationary guards in a polygonal region P, such that all points in P are guarded.

Abstract In this article, we propose a Lagrangian relaxation framework to solve the vertex separator problem (VSP). This framework is based on the development of relax‐and‐cut algorithms which embed the separation of valid inequalities for the VSP discussed by Balas and de Souza (Math Program 103 (2005), 583–608) in the subgradient method. These relax‐and‐cut algorithms are then used as a preprocessing phase in a hybrid algorithm which combines them with branch‐and‐cut algorithms proposed by de Souza and Balas (Math Program 103 (2005), 609–631). This is done basically by feeding the branch‐and‐cut algorithms not only with the primal bound but also the cuts separated during the preprocessing phase. Computational results obtained with benchmarks from the literature showed that the hybrid algorithm developed here outperforms the best exact algorithm available for the VSP to date. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

The Art Gallery problem (AGP) consists of minimizing the number of guards required to cover a gallery whose boundary is a simple polygon P . In this paper, we describe an Integer Programming based solution to agp that is presented in the accompanying video. Said solution is comprised of an exact algorithm that models discretizations of P as instances of the Set Cover problem and iteratively solves them using an IP solver. We have shown elsewhere [4] that this process always converges. A testing environment, shown in the video, has been implemented with which we have collected substantial experimental evidence that this approach is very efficient in practice, by solving instances of up to 2500 vertices.

In this article we consider the SONET ring assignment problem (SRAP) presented in 7. The authors pointed out the inadequacy of solving SRAP instances using their integer programming formulation and commercial linear programming solvers. Similar experiences with IP models for SRAP are reported in 1. In this article we reformulate SRAP as a set partitioning model with an additional knapsack constraint. This new formulation has an exponential number of columns and, to solve it, we implemented a branch-and-price/column generation algorithm. Extensive computational experiments showed that the new algorithm is orders of magnitude faster than standard branch-and-bound codes running on compact IP models introduced earlier. Instances taken from 1, 7, which could not be solved there in hours of computation were solved here to optimality in just a few seconds. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(3), 157–171 2006

Reconfigurable systems have been shown to achieve significant performance speedup through architectures that map the most time-consuming application kernel modules or inner loops to a reconfigurable datapath. As each portion of the application starts to execute, the system partially reconfigures the datapath so as to perform the corresponding computation. The reconfigurable datapath should have as few and simple hardware blocks and interconnections as possible, in order to reduce its cost, area, and reconfiguration overhead. To achieve that, hardware blocks and interconnections should be reused as much as possible across the application. We represent each piece of the application as a data-flow graph (DFG). The DFG merging process identifies similarities among the DFGs, and produces a single datapath that can be dynamically reconfigured and has a minimum area cost, when considering both hardware blocks and interconnections. In this paper we present a novel technique for the DFG merge problem, and we evaluate it using programs from the MediaBench benchmark. Our algorithm execution time approaches the fastest previous solution to this problem and produces datapaths with an average area reduction of 20%. When compared to the best known area solution, our approach produces datapaths with area costs equivalent to (and in many cases better than) it, while achieving impressive speedups.

Abstract Assume that a rectangle R is given on the Euclidean plane together with a finite set P of points that are interior to R. A rectangular partition of R is a partition of the surface of R into smaller rectangles. The length of such a partition equals the sum of the lengths for the line segments that define it. The partition is said to be feasible if no point of P is interior to a partition rectangle. The Rectangular Partitioning Problem (RPP) seeks a feasible rectangular partition of R with the least length. Computational evidence from the literature indicates that RPPs with noncorectilinear points in P, denoted NCRPPs, are the hardest to solve to proven optimality. In this paper, some structural properties of optimal feasible NCRPP partitions are presented. These properties allow substantial reductions in problem input size to be carried out. Additionally, a stronger formulation of the problem is also made possible. Based on these ingredients, a hybrid Lagrangian Relaxation—Linear Programming Relaxation exact solution algorithm is proposed. Such an algorithm has proved capable of solving NCRPP instances more than twice as large as those found in the literature. © 2002 Wiley Periodicals, Inc.