Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
New class of 0-1 integer programs with tight approximation via linear relaxations
Luleå tekniska universitet.
Institute of System Programming, Russian Academy of Sciences.
2001 (English)In: Mathematical Methods of Operations Research, ISSN 1432-2994, E-ISSN 1432-5217, Vol. 53, no 3, p. 363-370Article in journal (Refereed) Published
Abstract [en]

We consider the problem of estimating optima of integer programs { max cx | Axhb,0hxh1, x m integral} where b>0, cS0 are rational vectors and A is an arbitrary rational m 2n matrix. Using randomized rounding we find an efficiently verifiable sufficient condition for optima of such integer programs to be close to the optima q of their linear relaxations. We show that our condition guarantees that for any constant )>0 and sufficiently large n there exists a feasible integral solution z such that qS czS(1m))q.

Place, publisher, year, edition, pages
2001. Vol. 53, no 3, p. 363-370
National Category
Mathematical Analysis
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:ltu:diva-10772DOI: 10.1007/s001860100115Scopus ID: 2-s2.0-0034906432Local ID: 9a029ea0-aabf-11db-aeba-000ea68e967bOAI: oai:DiVA.org:ltu-10772DiVA, id: diva2:983719
Note

Validerad; 2001; 20070123 (evan)

Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Asratian, Armen S.
In the same journal
Mathematical Methods of Operations Research
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 5 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf