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 Nb00c9910397045529bbd468381f1f423
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 N3d81701ce3ea47d2add829d63b1c0b40
25 Ndafc5faeec7e41bebfc833df47281708
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 N105426d65c9c45a8a98dc5df3068d5bb
30 N2b84bfebdf714d4d862978e0a09bf2e0
31 Nf8f52ae2f729437da4b90c076080aa65
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 Nfa18b4306cac4f93bb2a634bad5d4d33
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 N105426d65c9c45a8a98dc5df3068d5bb schema:name readcube_id
42 schema:value 9830c7ab7f95bda9d9644ef9deda0ab7c9fa4f18f78903adecc2b6aa59c5ed81
43 rdf:type schema:PropertyValue
44 N2b84bfebdf714d4d862978e0a09bf2e0 schema:name dimensions_id
45 schema:value pub.1031947199
46 rdf:type schema:PropertyValue
47 N3d81701ce3ea47d2add829d63b1c0b40 schema:volumeNumber 67
48 rdf:type schema:PublicationVolume
49 N7b6c177ccc3a457fa04643a4d5c98155 rdf:first sg:person.01147516455.12
50 rdf:rest rdf:nil
51 Nb00c9910397045529bbd468381f1f423 rdf:first sg:person.011024647503.75
52 rdf:rest N7b6c177ccc3a457fa04643a4d5c98155
53 Ndafc5faeec7e41bebfc833df47281708 schema:issueNumber 1
54 rdf:type schema:PublicationIssue
55 Nf8f52ae2f729437da4b90c076080aa65 schema:name doi
56 schema:value 10.1007/s00186-007-0184-7
57 rdf:type schema:PropertyValue
58 Nfa18b4306cac4f93bb2a634bad5d4d33 schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
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)


...