We provide two new, simple proofs of Afriat’s celebrated theorem stating that a finite set of price-quantity observations is consistent with utility maximization if, and only if, the observations satisfy a variation of the Strong Axiom of Revealed Preference known as the Generalized Axiom of Revealed Preference. CitationTechnical Report No. 1381, School of Operations Research … Read more
We propose a new method for non-bijective graph matching for model-based pattern recognition. We formulate the search for the best correspondence between a model and an over-segmented image as a new combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together with the … Read more
A phylogenetic tree relates taxonomic units, based on their similarity over a set of characters. We propose a new genetic algorithm for the problem of building a phylogenetic tree under the parsimony criterion. This genetic algorithm makes use of an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originaly proposed … Read more
We give an algorithm for the following problem: given a graph $G=(V,E)$ with edge-weights and a nonnegative integer $k$, find a minimum cost set of edges that contains $k$ disjoint spanning trees. This also solves the following {\it reinforcement problem}: given a network, a number $k$ and a set of candidate edges, each of them … Read more
Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in Koster and Zymolka … Read more
A nonincreasing sequence of positive integers $\langle m_1,m_2,\cdots,m_k \rangle$ is said to be {\em $n$-realizable\/} if the set $I_n=\{ 1,2,\cdots,n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,\cdots, S_k$ such that $\sum\limits_{x\in S_i}x=m_i$ for each $1\le i\le k$. In this paper, we will prove that a nonincreasing sequence of positive integers $\langle m_1,m_2,\cdots,m_k\rangle$ is … Read more
An operation on trivalent graphs leads from the truncated cube to buckminsterfullerene, and C60 is the only fullerene with disjoint pentagons which can be obtained by this method. The construction and the proof emphasize maximal independent sets that contain two fifths of the vertices of trivalent graphs. In the case of C60, these sets define … Read more
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lov\’asz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures’ performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations … Read more
Taking a small graph, on which the randomized New-Best-In maximum clique heuristic fails to find the maximum clique, we construct on its basis a class of graphs exemplifying the inefficiency of SM greedy heuristics considered by Brockington and Culberson. We show that a 7(k+1)-vertex graph from this class is enough to provide a counterexample for … Read more
Arranging an n-vertex graph as the standard simplex in R^n, we identify graph cliques with simplex faces formed by clique vertices. An unstrict quadratic inequality holds for all points of the simplex; it turns to equality if and only if the point is on a face corresponding to a clique. This way this equality determines … Read more