Source author record

Sostenes L. Lins

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO math.GT

Catalog footprint

Research overview

2works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

An O(|E|)-linear Model for the MaxCut Problem

A polytope $P$ is a {\em model} for a combinatorial problem on finite graphs $G$ whose variables are indexed by the edge set $E$ of $G$ if the points of $P$ with (0,1)-coordinates are precisely the characteristic vectors of the subset of edges inducing the feasible configurations for the problem. In the case of the (simple) MaxCut Problem, which is the one that concern us here, the feasible subsets of edges are the ones inducing the bipartite subgraphs of $G$ . In this paper we introduce a new polytope $\mathbb{P}_{12} \subset \mathbb{R}^{|E|}$ given by at most $11|E|$ inequalities, which is a model for the MaxCut Problem on $G$ . Moreover, the left side of each inequality is the sum of at most 4 edge variables with coefficients $\pm1$ and right side 0,1, or 2. We restrict our analysis to the case of $G=K_{z}$ , the complete graph in $z$ vertices, where $z$ is an even positive integer $z\ge 4$ . This case is sufficient to study because the simple MaxCut problem for general graphs $G$ can be reduced to the complete graph $K_z$ by considering the obective function of the associated integer programming as the characteristic vector of the edges in $G \subseteq K_z$ . This is a polynomial algorithmic transformation.

preprint2013arXiv

A challenge to 3-manifold topologists and group algebraists

This paper poses some basic questions about instances (hard to find) of a special problem in 3-manifold topology. "Important though the general concepts and propositions may be with the modern industrious passion for axiomatizing and generalizing has presented us...nevertheless I am convinced that the special problems in all their complexity constitute the stock and the core of mathematics; and to master their difficulty requires on the whole the harder labor." Hermann Weyl 1885-1955, cited in the preface of the first edition (1939) of \cite{whitehead1997}.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.