Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
Parallel Approximation, and Integer Programming Reformulation
Date
2008-03-14
Author
Patakı, Gabor
Tural, Mustafa Kemal
Metadata
Show full item record
Item Usage Stats
145
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.