Results 41 to 50 of about 814 (113)
An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size [PDF]
, 2001 Given a complete undirected graph with the nodes partitioned into m node sets called clusters, the Generalized Minimum Spanning Tree problem denoted by GMST is to find a minimum-cost tree which includes exactly one node from each cluster.
Kern, W., Pop, P.C., Still, G.J.
core +1 more source
Covering compact metric spaces greedily
, 2018 A general greedy approach to construct coverings of compact metric spaces by metric balls is given and analyzed. The analysis is a continuous version of Chvatal's analysis of the greedy algorithm for the weighted set cover problem.
Rolfes, Jan Hendrik, Vallentin, Frank
core +1 more source
Discrete concavity and the half-plane property [PDF]
, 2009 Murota et al. have recently developed a theory of discrete convex analysis which concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over a field of generalized Puiseux series)
Buch A. S. +4 more
core +3 more sources
Intersection cuts from multiple rows: a disjunctive programming approach
EURO Journal on Computational Optimization, 2013 We address the issue of generating cutting planes for mixed integer programs from multiple rows of the simplex tableau with the tools of disjunctive programming.
Egon Balas, Andrea Qualizza
doaj +1 more source
The new FIFA rules are hard: Complexity aspects of sports competitions [PDF]
, 1999 Consider a soccer competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to win ...
Kern, W., Paulusma, D.
core +1 more source
Automatic boomerang attacks search on Rijndael
Journal of Mathematical CryptologyBoomerang attacks were introduced in 1999 by Wagner (The boomerang attack. In: Knudsen LR, editor. FSE’99. vol. 1636 of LNCS. Heidelberg: Springer; 1999. p.
Rouquette Loïc +2 more
doaj +1 more source
EURO Journal on Computational Optimization, 2017 The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods.
Thais Ávila +3 more
doaj +1 more source
Pattern Recognition on Oriented Matroids: Halfspaces, Convex Sets and Tope Committees [PDF]
, 2010 The principle of inclusion-exclusion is applied to subsets of maximal covectors contained in halfspaces of a simple oriented matroid and to convex subsets of its ground set for enumerating tope committees.Comment: 15 pages; v.2 - minor improvements, v.3 ...
Matveev, Andrey O.
core
THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND
Forum of Mathematics, Pi, 2013 The (real) Grothendieck constant ${K}_{G} $ is the infimum over those $K\in (0, \infty )$ such that for every $m, n\in \mathbb{N} $ and every $m\times n$ real matrix $({a}_{ij} )$ we have $$\begin{eqnarray*}\displaystyle \max _{\{ x_{i}\} _{i= 1}^{m} , \{
MARK BRAVERMAN +3 more
doaj +1 more source
On the theta number of powers of cycle graphs [PDF]
, 2011 We give a closed formula for Lovasz theta number of the powers of cycle graphs and of their complements, the circular complete graphs. As a consequence, we establish that the circular chromatic number of a circular perfect graph is computable in ...
Bachoc, Christine +2 more
core +3 more sources