We propose an exact algorithm for the Graph Burning Problem (GBP), an NP-hard optimization problem that models the spread of influence on social networks. Given a graph G with vertex set V, the objective is to find a sequence of k vertices in V, namely, v₁, v₂, … , v_k, such that k is minimum and ⋃_{i=1}^{k} {u∈V: d(u,v_i) ≤ k-i} = V, where d(u,v) denotes the distance between u and v. We formulate the problem as a set covering integer programming model and design a row generation algorithm for the GBP. Our method exploits the fact that a very small number of covering constraints is often sufficient for solving the integer model, allowing the corresponding rows to be generated on demand. To date, the most efficient exact algorithm for the GBP, denoted here by GDCA, is able to obtain optimal solutions for graphs with up to 14,000 vertices within two hours of execution. In comparison, our algorithm finds provably optimal solutions approximately 236 times faster, on average, than GDCA. For larger graphs, memory space becomes a limiting factor for GDCA. Our algorithm, however, solves real-world instances with more than 3 million vertices in less than 19 minutes, increasing the size of graphs for which optimal solutions are known by a factor of 200. Additionally, we conduct tests on the proposed algorithm using a series of challenging instances composed of grid graphs containing up to 5,000 vertices. As a result, we achieve novel optimal solutions and tight optimality gaps that have not been previously reported in the literature.

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.

The development of effective and efficient ways of handling real-world applications is becoming increasingly widespread, yet it still faces a number of practical challenges. First and foremost, we have the limited availability of labeled data in contrast to an unbounded number of unlabeled ones. Despite some efforts in active semi-supervised learning, their success depends on an approach suitable to be applied to real massive data. In this paper, we introduce a novel integration of semi-supervised learning and a priori-reduction and organization criteria for active learning based on Optimum-Path Forest classifiers. Encouraging results on both public and real data show the synergy of these strategies jointly. Our approach iteratively generates semi-supervised classifiers that attain high accuracy by selecting the most representative labeled set, while decreasing the propagated errors on the unlabeled set. In addition, it is able to identify samples from all classes quickly while keeping user interaction to a minimum throughout the learning iterations.

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.

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.

The oriented projective plane T2 is an extension of the Euclidean plane E2 and comprises a number of advantages for algorithm design and implementation. We have extended the Computational Geometry Algorithms Library (CGAL) to allow for the implementation of geometric primitives and algorithms. The present video illustrates both the extension of a few algorithms to T2 under CGAL and a dynamic visualization system (T2 Viewer)built specially for displaying the spherical and planar models of T2.

The accompanying videotape presents two animation modes provided by the Geometric Laboratory GeoLab which we have developed as a programming environment for implementation, testing and animation of geometric algorithsm. GeoLab runs on SparcStations under Sun/OS using the XView graphics library, following the OpenLook graphical user interface guidelines.

We address ourselves to an instance of the Shortest Path problem with obstacles where a shortest path in the Manhattan (or L1) distance is sought between two points (source and destination) and the obstacles are n disjoint rectangles with sides parallel to the coordinate axes. A plane sweep technique is applied rather than the graph theoretic approach frequently used in the literature. We show that there has to be a path of minimum length between the two given points which is monotone in at least one of x or y directions. Then we present an algorithm of time complexity Ο(n log n) for constructing that path and show that our algorithm is optimal.