𝔖 Bobbio Scriptorium
✦   LIBER   ✦

O(n log n) procedures for tightening cover inequalities

✍ Scribed by L.F. Escudero; A. Garı́n; G. Pérez

Book ID
104339763
Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
153 KB
Volume
113
Category
Article
ISSN
0377-2217

No coin nor oath required. For personal study only.

✦ Synopsis

We present two procedures for tightening cover induced inequalities in 0-1 programs by using knapsack constraints plus some other information from the program. The tightening is obtained by solving successive knapsack problems with all 0-1 objective function coecients, and using dominance criteria to avoid the explicit solving of some knapsack problems. The new constraints are 0-1 equivalent to and LP tighter than the original ones. Both procedures have On log n complexity, where n is the number of variables with nonzero coecients in the knapsack constraint, however one of them can strongly reduce the computational eort. Some computational experience is reported.

📜 SIMILAR VOLUMES

An n log n Algorithm for Onlin
An n log n Algorithm for Online BDD Refinement
✍ Nils Klarlund 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 177 KB

Binary decision diagrams are in widespread use in verification systems for the canonical representation of finite functions. Here we consider multivalued BDDs, which represent functions of the form : ‫ނ‬ ª L L , where L L is a finite set of leaves. We study a rather natural online BDD refinement pro

AnO(m + n log n) Alg
AnO(m + n log n) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
✍ Binay K. Bhattacharya; Damon Kaller 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 338 KB

We present an algorithm to compute, in O m q n log n time, a maximum clique Ž . in circular-arc graphs with n vertices and m edges provided a circular-arc model of the graph is given. If the circular-arc endpoints are given in sorted order, the Ž . time complexity is O m . The algorithm operates on

A direct O(N log2 N) finite di
A direct O(N log2 N) finite difference method for fractional diffusion equations
✍ Hong Wang; Kaixin Wang; Treena Sircar 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 308 KB

Fractional diffusion equations model phenomena exhibiting anomalous diffusion that can not be modeled accurately by the second-order diffusion equations. Because of the nonlocal property of fractional differential operators, the numerical methods have full coefficient matrices which require storage

Non-Ramsey Graphs Are c log n-
Non-Ramsey Graphs Are c log n-Universal
✍ Hans Jürgen Prömel; Vojtěch Rödl 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 98 KB

We prove that for any c 1 >0 there exists c 2 >0 such that the following statement is true: If G is a graph with n vertices and with the property that neither G nor its complement contains a complete graph K l , where l=c 1 log n then G is c 2 log n-universal, i.e., G contains all subgraphs with c 2