BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Diego Delle Donne

Diego Delle Donne appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete MathematicsData Structures and Algorithmsmath.COmath.OC

Catalog footprint

What is connected

3works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

3 published item(s)

preprint2020arXiv

MIP and Set Covering approaches for Sparse Approximation

The Sparse Approximation problem asks to find a solution $x$ such that $||y - Hx|| < α$, for a given norm $||\cdot||$, minimizing the size of the support $||x||_0 := \#\{j \ |\ x_j \neq 0 \}$. We present valid inequalities for Mixed Integer Programming (MIP) formulations for this problem and we show that these families are sufficient to describe the set of feasible supports. This leads to a reformulation of the problem as an Integer Programming (IP) model which in turn represents a Minimum Set Covering formulation, thus yielding many families of valid inequalities which may be used to strengthen the models up. We propose algorithms to solve sparse approximation problems including a branch \& cut for the MIP, a two-stages algorithm to tackle the set covering IP and a heuristic approach based on Local Branching type constraints. These methods are compared in a computational experimentation with the goal of testing their practical potential.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Bit-Parallel Russian Dolls Search for a Maximum Cardinality Clique in a Graph

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Polyhedral studies of vertex coloring problems: The asymmetric representatives formulation

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.

0 citations0 reviewsNo code linkedOpen access