Search

A set of points $X = X_B \cup X_R \subseteq \mathbb{R}^d$ is linearly separable if the convex hulls of $X_B$ and $X_R$ are disjoint, hence there exists a hyperplane separating $X_B$ from $X_R$. Such a hyperplane provides a method for classifying new points, according to which side of the hyperplane the new points lie. When such a linear separation is not possible, it may still be possible to partition $X_B$ and $X_R$ into prespecified numbers of groups, in such a way that every group from $X_B$ is linearly separable from every group from $X_R$. We may also discard some points as outliers, and seek to minimize the number of outliers necessary to find such a partition. Based on these ideas, Bertsimas and Shioda proposed the classification and regression by integer optimization (CRIO) method in 2007. In this work we explore the integer programming aspects of the classification part of CRIO, in particular theoretical properties of the associated formulation. We are able to find facet-inducing inequalities coming from the stable set polytope, hence showing that this classification problem has exploitable combinatorial properties., Comment: 22 pages, 4 figures

We propose general separation procedures for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and Camp\^{e}lo. In contrast to existing cut-generating procedures, ours generate both rank and non-rank valid inequalities, hence they are of a more general nature than existing methods. This is accomplished by iteratively solving a lifting problem, which consists of a maximum weighted stable set problem on a smaller graph. Computational experience on DIMACS benchmark instances shows that the proposed approach may be a useful tool for generating cuts for the stable set polytope.

Despite the fact that some vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not "under control" from a polyhedral point of view. The equivalence between \emph{optimization} and \emph{polyhedral separation} suggests that, for these problems, there must exist formulations admitting some elegant characterization for the polytopes associated to them. Therefore, it is interesting to study known formulations for vertex coloring with the goal of finding such characterizations. In this work we study the asymmetric representatives formulation and we show that the corresponding coloring polytope, for a given graph $G$, can be interpreted as the stable set polytope of another graph obtained from $G$. This result allows us to derive complete characterizations for the corresponding coloring polytope for some families of graphs, based on known complete characterizations for the stable set polytope.

Finding the clique of maximum cardinality in an arbitrary graph is an NP-Hard problem that has many applications, which has motivated studies to solve it exactly despite its difficulty. The great majority of algorithms proposed in the literature are based on the Branch and Bound method. In this paper, we propose an exact algorithm for the maximum clique problem based on the Russian Dolls Search method. When compared to Branch and Bound, the main difference of the Russian Dolls method is that the nodes of its search tree correspond to decision subproblems, instead of the optimization subproblems of the Branch and Bound method. In comparison to a first implementation of this Russian Dolls method from the literature, several improvements are presented. Some of them are adaptations of techniques already employed successfully in Branch and Bound algorithms, like the use of approximate coloring for pruning purposes and bit-parallel operations. Two different coloring heuristics are tested: the standard greedy and the greedy with recoloring. Other improvements are directly related to the Russian Dolls scheme: the adoption of recursive calls where each subproblem (doll) is solved itself via the same principles than the Russian Dolls Search and the application of an elimination rule allowing not to generate a significant number of dolls. Results of computational experiments show that the algorithm outperforms the best exact combinatorial algorithms in the literature for the great majority of the dense graphs tested, being more than twice faster in several cases.

The maximal sum of a sequence "A" of "n" real numbers is the greatest sum of all elements of any strictly contiguous and possibly empty subsequence of "A", and it can be computed in "O(n)" time by means of Kadane's algorithm. Letting "A^(x -> p)" denote the sequence which results from inserting a real number "x" between elements "A[p-1]" and "A[p]", we show how the maximal sum of "A^(x -> p)" can be computed in "O(1)" worst-case time for any given "x" and "p", provided that an "O(n)" time preprocessing step has already been executed on "A". In particular, this implies that, given "m" pairs "(x_0, p_0), ..., (x_{m-1}, p_{m-1})", we can compute the maximal sums of sequences "A^(x_0 -> p_0), ..., A^(x_{m-1} -> p_{m-1})" in "O(n+m)" time, which matches the lower bound imposed by the problem input size, and also improves on the straightforward strategy of applying Kadane's algorithm to each sequence "A^(x_i -> p_i)", which takes a total of "Theta(n.m)" time. Our main contribution, however, is to obtain the same time bound for the more complicated problem of computing the greatest sum of all elements of any strictly or circularly contiguous and possibly empty subsequence of "A^(x -> p)". Our algorithms are easy to implement in practice, and they were motivated by and find application in a buffer minimization problem on wireless mesh networks., Comment: 13 pages, 4 figures, 2 tables. Accepted for journal publication

Let $A$ be a sequence of $n \geq 0$ real numbers. A subsequence of $A$ is a sequence of contiguous elements of $A$. A \emph{maximum scoring subsequence} of $A$ is a subsequence with largest sum of its elements, which can be found in O(n) time by Kadane's dynamic programming algorithm. We consider in this paper two problems involving maximal scoring subsequences of a sequence. Both of these problems arise in the context of buffer memory minimization in computer networks. The first one, which is called {\sc Insertion in a Sequence with Scores (ISS)}, consists in inserting a given real number $x$ in $A$ in such a way to minimize the sum of a maximum scoring subsequence of the resulting sequence, which can be easily done in $O(n^2)$ time by successively applying Kadane's algorithm to compute the maximum scoring subsequence of the resulting sequence corresponding to each possible insertion position for $x$. We show in this paper that the ISS problem can be solved in linear time and space with a more specialized algorithm. The second problem we consider in this paper is the {\sc Sorting a Sequence by Scores (SSS)} one, stated as follows: find a permutation $A'$ of $A$ that minimizes the sum of a maximum scoring subsequence. We show that the SSS problem is strongly NP-Hard and give a 2-approximation algorithm for it., Comment: This paper has been submitted for journal publication

A k-fold x-coloring of a graph is an assignment of (at least) k distinct colors from the set {1, 2, ..., x} to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The smallest number x such that G admits a k-fold x-coloring is the k-th chromatic number of G, denoted by \chi_k(G). We determine the exact value of this parameter when G is a web or an antiweb. Our results generalize the known corresponding results for odd cycles and imply necessary and sufficient conditions under which \chi_k(G) attains its lower and upper bounds based on the clique, the fractional chromatic and the chromatic numbers. Additionally, we extend the concept of \chi-critical graphs to \chi_k-critical graphs. We identify the webs and antiwebs having this property, for every integer k <= 1., Comment: A short version of this paper was presented at the Simp\'osio Brasileiro de Pesquisa Operacional, Brazil, 2011

We propose a new integer programming formulation for the problem of finding a maximum stable set of a graph based on representatives of stable sets. In addition, we investigate exact solutions provided by a Lagrangian decomposition of this formulation in which only one constraint is relaxed. Some computational experiments were carried out with an effective multi-threaded implementation of our algorithm in a multi-core system, and their results are presented., Comment: Submitted to International Transactions on Operations Research

Asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions induced by restricting nondeterminism are more efficient, in an application-specific sense, than the others. In this work, we define partially ordered executions of a distributed algorithm as the executions satisfying some restricted orders of their actions in two different frameworks, those of the so-called event- and pulse-driven computations. The aim of these restrictions is to characterize asynchronous executions that are likely to be more efficient for some important classes of applications. Also, an asynchronous algorithm that ensures the occurrence of partially ordered executions is given for each case. Two of the applications that we believe may benefit from the restricted nondeterminism are backtrack search, in the event-driven case, and iterative algorithms for systems of linear equations, in the pulse-driven case.