Vector and matrix apportionment problems and separable convex integer optimization View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2008-02

AUTHORS

N. Gaffke, F. Pukelsheim

ABSTRACT

The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure. More... »

PAGES

133-159

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00186-007-0184-7

DOI

http://dx.doi.org/10.1007/s00186-007-0184-7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1031947199


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Otto-von-Guericke University Magdeburg", 
          "id": "https://www.grid.ac/institutes/grid.5807.a", 
          "name": [
            "Faculty of Mathematics, University of Magdeburg, PF 4120, 39016, Magdeburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gaffke", 
        "givenName": "N.", 
        "id": "sg:person.011024647503.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011024647503.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Augsburg", 
          "id": "https://www.grid.ac/institutes/grid.7307.3", 
          "name": [
            "Institute of Mathematics, University of Augsburg, 86135, Augsburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pukelsheim", 
        "givenName": "F.", 
        "id": "sg:person.01147516455.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01147516455.12"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-35605-3_3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000844092", 
          "https://doi.org/10.1007/3-540-35605-3_3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01589103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003890771", 
          "https://doi.org/10.1007/bf01589103"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1524/strm.1996.14.4.373", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015845439"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/96559.96597", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016937184"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.mathsocsci.2008.01.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019178560"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.orl.2003.11.007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024605330"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02614622", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025570603", 
          "https://doi.org/10.1007/bf02614622"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02614622", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025570603", 
          "https://doi.org/10.1007/bf02614622"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0378-3758(99)00077-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041043428"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01582246", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043970463", 
          "https://doi.org/10.1007/bf01582246"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02925514", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045930866", 
          "https://doi.org/10.1007/bf02925514"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02925514", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045930866", 
          "https://doi.org/10.1007/bf02925514"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01681344", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048539756", 
          "https://doi.org/10.1007/bf01681344"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01681344", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048539756", 
          "https://doi.org/10.1007/bf01681344"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/j.1467-9574.1978.tb01397.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048955827"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ro/1986200201231", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1083713864"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/9789812798190_0015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088704610"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2008-02", 
    "datePublishedReg": "2008-02-01", 
    "description": "The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193\u2013210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00186-007-0184-7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1053187", 
        "issn": [
          "1432-2994", 
          "1432-5217"
        ], 
        "name": "Mathematical Methods of Operations Research", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "67"
      }
    ], 
    "name": "Vector and matrix apportionment problems and separable convex integer optimization", 
    "pagination": "133-159", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "9830c7ab7f95bda9d9644ef9deda0ab7c9fa4f18f78903adecc2b6aa59c5ed81"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00186-007-0184-7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031947199"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00186-007-0184-7", 
      "https://app.dimensions.ai/details/publication/pub.1031947199"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T14:34", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000373_0000000373/records_13109_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00186-007-0184-7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00186-007-0184-7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00186-007-0184-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00186-007-0184-7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00186-007-0184-7'


 

This table displays all metadata directly associated to this object as RDF triples.

119 TRIPLES      21 PREDICATES      41 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00186-007-0184-7 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N415d48c205844fe385d06af651485abc
4 schema:citation sg:pub.10.1007/3-540-35605-3_3
5 sg:pub.10.1007/bf01582246
6 sg:pub.10.1007/bf01589103
7 sg:pub.10.1007/bf01681344
8 sg:pub.10.1007/bf02614622
9 sg:pub.10.1007/bf02925514
10 https://doi.org/10.1016/j.mathsocsci.2008.01.004
11 https://doi.org/10.1016/j.orl.2003.11.007
12 https://doi.org/10.1016/s0378-3758(99)00077-4
13 https://doi.org/10.1051/ro/1986200201231
14 https://doi.org/10.1111/j.1467-9574.1978.tb01397.x
15 https://doi.org/10.1142/9789812798190_0015
16 https://doi.org/10.1145/96559.96597
17 https://doi.org/10.1524/strm.1996.14.4.373
18 schema:datePublished 2008-02
19 schema:datePublishedReg 2008-02-01
20 schema:description The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.
21 schema:genre research_article
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf N8e610b83c0e14e22ae6d599771fc4292
25 Nc2fa1c9364114f89bec0317470c0da90
26 sg:journal.1053187
27 schema:name Vector and matrix apportionment problems and separable convex integer optimization
28 schema:pagination 133-159
29 schema:productId N5165fcd0efcc40aeb5468744670902aa
30 N9e20b19d6fe745e8b03f16e6ef9fad48
31 Ne7159d2cbcbf4eb99ecdfd7263f5fcda
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031947199
33 https://doi.org/10.1007/s00186-007-0184-7
34 schema:sdDatePublished 2019-04-11T14:34
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher Nb476629e14fc4ef8ba21c25bd274a932
37 schema:url http://link.springer.com/10.1007/s00186-007-0184-7
38 sgo:license sg:explorer/license/
39 sgo:sdDataset articles
40 rdf:type schema:ScholarlyArticle
41 N1f53ac023581408b9586c988081f6351 rdf:first sg:person.01147516455.12
42 rdf:rest rdf:nil
43 N415d48c205844fe385d06af651485abc rdf:first sg:person.011024647503.75
44 rdf:rest N1f53ac023581408b9586c988081f6351
45 N5165fcd0efcc40aeb5468744670902aa schema:name doi
46 schema:value 10.1007/s00186-007-0184-7
47 rdf:type schema:PropertyValue
48 N8e610b83c0e14e22ae6d599771fc4292 schema:volumeNumber 67
49 rdf:type schema:PublicationVolume
50 N9e20b19d6fe745e8b03f16e6ef9fad48 schema:name readcube_id
51 schema:value 9830c7ab7f95bda9d9644ef9deda0ab7c9fa4f18f78903adecc2b6aa59c5ed81
52 rdf:type schema:PropertyValue
53 Nb476629e14fc4ef8ba21c25bd274a932 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 Nc2fa1c9364114f89bec0317470c0da90 schema:issueNumber 1
56 rdf:type schema:PublicationIssue
57 Ne7159d2cbcbf4eb99ecdfd7263f5fcda schema:name dimensions_id
58 schema:value pub.1031947199
59 rdf:type schema:PropertyValue
60 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
61 schema:name Mathematical Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
64 schema:name Numerical and Computational Mathematics
65 rdf:type schema:DefinedTerm
66 sg:journal.1053187 schema:issn 1432-2994
67 1432-5217
68 schema:name Mathematical Methods of Operations Research
69 rdf:type schema:Periodical
70 sg:person.011024647503.75 schema:affiliation https://www.grid.ac/institutes/grid.5807.a
71 schema:familyName Gaffke
72 schema:givenName N.
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011024647503.75
74 rdf:type schema:Person
75 sg:person.01147516455.12 schema:affiliation https://www.grid.ac/institutes/grid.7307.3
76 schema:familyName Pukelsheim
77 schema:givenName F.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01147516455.12
79 rdf:type schema:Person
80 sg:pub.10.1007/3-540-35605-3_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000844092
81 https://doi.org/10.1007/3-540-35605-3_3
82 rdf:type schema:CreativeWork
83 sg:pub.10.1007/bf01582246 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043970463
84 https://doi.org/10.1007/bf01582246
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/bf01589103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003890771
87 https://doi.org/10.1007/bf01589103
88 rdf:type schema:CreativeWork
89 sg:pub.10.1007/bf01681344 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048539756
90 https://doi.org/10.1007/bf01681344
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/bf02614622 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025570603
93 https://doi.org/10.1007/bf02614622
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/bf02925514 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045930866
96 https://doi.org/10.1007/bf02925514
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/j.mathsocsci.2008.01.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019178560
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/j.orl.2003.11.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024605330
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/s0378-3758(99)00077-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041043428
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1051/ro/1986200201231 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083713864
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1111/j.1467-9574.1978.tb01397.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048955827
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1142/9789812798190_0015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088704610
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1145/96559.96597 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016937184
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1524/strm.1996.14.4.373 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015845439
113 rdf:type schema:CreativeWork
114 https://www.grid.ac/institutes/grid.5807.a schema:alternateName Otto-von-Guericke University Magdeburg
115 schema:name Faculty of Mathematics, University of Magdeburg, PF 4120, 39016, Magdeburg, Germany
116 rdf:type schema:Organization
117 https://www.grid.ac/institutes/grid.7307.3 schema:alternateName University of Augsburg
118 schema:name Institute of Mathematics, University of Augsburg, 86135, Augsburg, Germany
119 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...