Search

The adjacency of two vertices on an arbitrary 0–1-polyhedron P is characterized by certain criteria involving the (prime) implicants of P, which are generalizations of the circuits of an independence system. These criteria can be checked by straightforward “colouring algorithms”. They are sufficient for all 0–1-polyhedra and necessary for at least three classes containing the polyhedra of many well-known discrete optimization problems, e.g. the vertex packing problem, set packing problem, vertex covering problem, matching problem, assignment problem, partitioning problem, linear ordering problem, partial ordering problem.

It is pointed out that problems like the Set Covering problem, the Set Packing problem or the problem of deter-mining whether a graph is Hamiltonian admit, for arbitrary values of the parameters like the dimensions of the matrices in the first two problems or the number of points in the third problem, an onionlike structure for the set of problems that correspond to the parameter values.

Many important combinatorial optimization problems, including the traveling salesman problem (TSP), the clique problem and many others, call for the optimization of a linear functional over some discrete set of vectors.

The (bounded) generalized maximum satisfiability problem covers a broad range of NP-complete problems, e.g. it is a generalization of INDEPENDENT SET, LINEAR INEQUALITY, HITTING SET, SET PACKING, MINIMUM COVER, etc. The complexity of finding approximations for problems in this class is analyzed. The results have several interpretations, including the following: - A general class of existence proofs is made efficiently constructive. - A class of randomized algorithms is made deterministic and efficient. - A new class of combinatorial approximation algorithms is introduced, which is based on “background” optimization. Instead of maximizing among all assignments we maximize among expected values for parametrized random solutions. It turns out that this “background” optimization is in two precise senses best possible if P≠NP. The “background optimization” performed is equivalent to finding the maximum of a polynomial in a bounded region.

In this paper, we propose a global, self- explainable solution to solve a prominent NLP problem: Entity Resolution (ER). We formu- late ER as a graph partitioning problem. Every mention of a real-world entity is represented by a node in the graph, and the pairwise sim- ilarity scores between the mentions are used to associate these nodes to exactly one clique, which represents a real-world entity in the ER domain. In this paper, we use Clique Partition- ing Problem (CPP), which is an Integer Pro- gram (IP) to formulate ER as a graph partition- ing problem and then highlight the explainable nature of this method. Since CPP is NP-Hard, we introduce an efficient solution procedure, the xER algorithm, to solve CPP as a combi- nation of finding maximal cliques in the graph and then performing generalized set packing using a novel formulation. We discuss the advantages of using xER over the traditional methods and provide the computational exper- iments and results of applying this method to ER data sets.

As a part of a heuristic for the fast detection of new word combinations in text streams, we consider the NP-hard Partial Set Cover of Pairs problem. There we wish to cover a maximum number of pairs of elements by a prescribed number of sets from a given set family. While the approximation ratio of the greedy algorithm for the classic Partial Set Cover problem is completely understood, the same question for covering of pairs is intrinsically more complicated, since the pairs insert some graph-theoretic structure. The best approximation guarantee for the first greedy step can be rephrased as a problem in extremal combinatorics: Assume that we may place a fixed number of subsets of fixed and equal size in a set, how many different pairs of elements can we cover? In this paper we introduce a method to calculate optimal approximation guarantees, and we demonstrate its use on the smallest set families.

A ρ-independent set S in a graph is parameterized by a set ρ of non-negative integers that constrains how the independent set S can dominate the remaining vertices (∀υ ¬∈ S: |N(υ)∩S| ∈ ρ.) For all values of ρ, we classify as either, N P-complete or polynomial-time solvable the problems of deciding if a given graph has a ρ-independent set. We complement this with approximation algorithms and inapproximability results, for all the corresponding optimization problems. These approximation results extend also to several related independence problems. In particular, we obtain a √m approximation of the Set Packing problem, where m is the number of base elements, as well as a √n approximation of the maximum independent set in power graphs G', for t even.

This note discusses the reduction of the set basis problem to the clique cover problem.