Parallel Approximation, and Integer Programming Reformulation

Date

2008-03-14

Author

Patakı, Gabor
Tural, Mustafa Kemal

Metadata

Show full item record

Item Usage Stats

172
views

0
downloads

We show that in a knapsack feasibility problem an integral vectorp, which is short, and nearparallel to the constraint vector gives a branching direction with small integer width.We use this result to analyze two computationally efficient reformulation techniques on lowdensity knapsack problems. Both reformulations have a constraint matrix with columns reducedin the sense of Lenstra, Lenstra, and Lov ́asz. We prove an upper bound on the integer widthalong the last variable, which becomes 1,when the density is sufficiently small.In the proof we extract from the transformation matrices a vector which is near parallel tothe constraint vectora.The near parallel vector is a good branching direction in the originalknapsack problem, and this transfers to the last variable in the reformulations

URI

https://hdl.handle.net/11511/78732
chrome-extension://dagcmkpagjlhakfdhnbomgmjdpkdklff/enhanced-reader.html?openApp&pdf=https%3A%2F%2Farxiv.org%2Fpdf%2F0807.3355.pdf

Conference Name

INFORMS Optimization Society Conference 2008, (14 - 16 Mart 2008)

Collections

Department of Industrial Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Invariant densities and mean ergodicity of Markov operators Emelyanov, Eduard (2003-01-01) We prove that a, Markov operator T on L-1 has an invariant density if and only if there exists a density f that satisfies lim sup(n-->infinity) parallel toT(n) f-fparallel to infinity) parallel toP(n)f - wparallel to < 2 for every density f. Corresponding results hold for strongly continuous semigroups.
Galois structure of modular forms of even weight Gurel, E. (Elsevier BV, 2009-10-01) We calculate the equivariant Euler characteristics of powers of the canonical sheaf on certain modular curves over Z which have a tame action of a finite abelian group. As a consequence, we obtain information on the Galois module structure of modular forms of even weight having Fourier coefficients in certain ideals of rings of cyclotomic algebraic integers. (c) 2009 Elsevier Inc. All rights reserved.
Fuzzy optimization for portfolio selection based on Embedding Theorem in Fuzzy Normed Linear Spaces Solatikia, Farnaz; Kiliç, Erdem; Weber, Gerhard Wilhelm (Walter de Gruyter GmbH, 2014-5-1) <jats:title>Abstract</jats:title> <jats:p>Background: This paper generalizes the results of Embedding problem of Fuzzy Number Space and its extension into a Fuzzy Banach Space C(Ω) × C(Ω), where C(Ω) is the set of all real-valued continuous functions on an open set Ω. </jats:p> <jats:p>Objectives: The main idea behind our approach consists of taking advantage of interplays between fuzzy normed spaces and normed spaces in a way to get an equivalent stochastic program. This helps avoiding pitfalls d...
Knotting of algebraic curves in CP2 Finashin, Sergey (2002-01-01) For any k⩾3, I construct infinitely many pairwise smoothly non-isotopic smooth surfaces homeomorphic to a non-singular algebraic curve of degree 2k, realizing the same homology class as such a curve and having abelian fundamental group ⧹ . This gives an answer to Problem 4.110 in the Kirby list (Kirby, Problems in low-dimensional topology, in: W. Kazez (Ed.), Geometric Topology, AMS/IP Stud. Adv. Math. vol 2.2, Amer. Math. Soc., Providence, 1997).
Numerical Constructions of Testing Functions for Improving the Accuracy of MFIE and CFIE in Multi-Frequency Applications Karaosmanoglu, Bariscan; Altinoklu, Askin; Ergül, Özgür Salih (EMW Publishing, 2016-01-01) We present a new approach based on numerical constructions of testing functions for improving the accuracy of the magnetic-field integral equation (MFIE) and the combined-field integral equation (CFIE) with low-order discretizations. Considering numerical solutions, testing functions are designed by enforcing the compatibility of the MFIE systems with the accurate coefficients obtained by solving the electric-field integral equation (EFIE). We demonstrate the accuracy improvements on scattering problems, wh...

Citation Formats

G. Patakı and M. K. Tural, “Parallel Approximation, and Integer Programming Reformulation,” presented at the INFORMS Optimization Society Conference 2008, (14 - 16 Mart 2008), Amerika Birleşik Devletleri, 2008, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/78732.