An Algorithm for Solving an Overdetermined Tropical Linear System Using the Analysis of Stable Solutions of Subsystems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-07

AUTHORS

A. Davydow

ABSTRACT

In this paper, we show that an overdetermined tropical linear system has a solution if and only if it contains a square subsystem having a stable solution that is a solution of the original system. This leads to a simple algorithm for solving tropical linear systems in time Onmn4, where m is the number of equations and n is the number of variables. For weakly overdetermined systems, this time is polynomial. More... »

PAGES

25-35

References to SciGraph publications

  • 2013-03. Complexity of Solving Tropical Linear Systems in COMPUTATIONAL COMPLEXITY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10958-018-3856-3

    DOI

    http://dx.doi.org/10.1007/s10958-018-3856-3

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure 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": "Saint Petersburg Academic University", 
              "id": "https://www.grid.ac/institutes/grid.35135.31", 
              "name": [
                "St. Petersburg Academic University, St. Petersburg, Russia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Davydow", 
            "givenName": "A.", 
            "id": "sg:person.013317615563.62", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013317615563.62"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0166-218x(92)00104-t", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004992278"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00927870902828793", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012892446"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00037-012-0053-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019985194", 
              "https://doi.org/10.1007/s00037-012-0053-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/nav.3800020109", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032778056"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jsc.2005.11.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032968943"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/09075024x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062856031"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0218196711006674", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062961627"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.4171/rmi/561", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1072320881"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/conm/377/06998", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1089201463"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-07", 
        "datePublishedReg": "2018-07-01", 
        "description": "In this paper, we show that an overdetermined tropical linear system has a solution if and only if it contains a square subsystem having a stable solution that is a solution of the original system. This leads to a simple algorithm for solving tropical linear systems in time Onmn4, where m is the number of equations and n is the number of variables. For weakly overdetermined systems, this time is polynomial.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s10958-018-3856-3", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136516", 
            "issn": [
              "1072-3374", 
              "1573-8795"
            ], 
            "name": "Journal of Mathematical Sciences", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "232"
          }
        ], 
        "name": "An Algorithm for Solving an Overdetermined Tropical Linear System Using the Analysis of Stable Solutions of Subsystems", 
        "pagination": "25-35", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a9a631a135433667e9df92246d2d7c50a003bc7cfecc4cb5c02b2b6073c9986c"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10958-018-3856-3"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1104214075"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10958-018-3856-3", 
          "https://app.dimensions.ai/details/publication/pub.1104214075"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T10:39", 
        "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/0000000349_0000000349/records_113679_00000004.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://link.springer.com/10.1007%2Fs10958-018-3856-3"
      }
    ]
     

    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/s10958-018-3856-3'

    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/s10958-018-3856-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10958-018-3856-3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10958-018-3856-3'


     

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

    89 TRIPLES      21 PREDICATES      36 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10958-018-3856-3 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N90cdbb030f5942438f06c26d7cb0939a
    4 schema:citation sg:pub.10.1007/s00037-012-0053-5
    5 https://doi.org/10.1002/nav.3800020109
    6 https://doi.org/10.1016/0166-218x(92)00104-t
    7 https://doi.org/10.1016/j.jsc.2005.11.006
    8 https://doi.org/10.1080/00927870902828793
    9 https://doi.org/10.1090/conm/377/06998
    10 https://doi.org/10.1137/09075024x
    11 https://doi.org/10.1142/s0218196711006674
    12 https://doi.org/10.4171/rmi/561
    13 schema:datePublished 2018-07
    14 schema:datePublishedReg 2018-07-01
    15 schema:description In this paper, we show that an overdetermined tropical linear system has a solution if and only if it contains a square subsystem having a stable solution that is a solution of the original system. This leads to a simple algorithm for solving tropical linear systems in time Onmn4, where m is the number of equations and n is the number of variables. For weakly overdetermined systems, this time is polynomial.
    16 schema:genre research_article
    17 schema:inLanguage en
    18 schema:isAccessibleForFree false
    19 schema:isPartOf N836d26a11501440a86256a38d955ea5e
    20 Nf88e40cb187047788db764d510f2b8df
    21 sg:journal.1136516
    22 schema:name An Algorithm for Solving an Overdetermined Tropical Linear System Using the Analysis of Stable Solutions of Subsystems
    23 schema:pagination 25-35
    24 schema:productId N3cc84613c50c4af0945ad0d07d17e9e2
    25 N98a4365cf4e449b4ae5d92a0a7d27101
    26 Nd44753d8b69f43089e869b563469b8b6
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1104214075
    28 https://doi.org/10.1007/s10958-018-3856-3
    29 schema:sdDatePublished 2019-04-11T10:39
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher Nf5ef5e39409a48b18d2bac08c6cf42aa
    32 schema:url https://link.springer.com/10.1007%2Fs10958-018-3856-3
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset articles
    35 rdf:type schema:ScholarlyArticle
    36 N3cc84613c50c4af0945ad0d07d17e9e2 schema:name dimensions_id
    37 schema:value pub.1104214075
    38 rdf:type schema:PropertyValue
    39 N836d26a11501440a86256a38d955ea5e schema:volumeNumber 232
    40 rdf:type schema:PublicationVolume
    41 N90cdbb030f5942438f06c26d7cb0939a rdf:first sg:person.013317615563.62
    42 rdf:rest rdf:nil
    43 N98a4365cf4e449b4ae5d92a0a7d27101 schema:name readcube_id
    44 schema:value a9a631a135433667e9df92246d2d7c50a003bc7cfecc4cb5c02b2b6073c9986c
    45 rdf:type schema:PropertyValue
    46 Nd44753d8b69f43089e869b563469b8b6 schema:name doi
    47 schema:value 10.1007/s10958-018-3856-3
    48 rdf:type schema:PropertyValue
    49 Nf5ef5e39409a48b18d2bac08c6cf42aa schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 Nf88e40cb187047788db764d510f2b8df schema:issueNumber 1
    52 rdf:type schema:PublicationIssue
    53 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    54 schema:name Mathematical Sciences
    55 rdf:type schema:DefinedTerm
    56 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Pure Mathematics
    58 rdf:type schema:DefinedTerm
    59 sg:journal.1136516 schema:issn 1072-3374
    60 1573-8795
    61 schema:name Journal of Mathematical Sciences
    62 rdf:type schema:Periodical
    63 sg:person.013317615563.62 schema:affiliation https://www.grid.ac/institutes/grid.35135.31
    64 schema:familyName Davydow
    65 schema:givenName A.
    66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013317615563.62
    67 rdf:type schema:Person
    68 sg:pub.10.1007/s00037-012-0053-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019985194
    69 https://doi.org/10.1007/s00037-012-0053-5
    70 rdf:type schema:CreativeWork
    71 https://doi.org/10.1002/nav.3800020109 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032778056
    72 rdf:type schema:CreativeWork
    73 https://doi.org/10.1016/0166-218x(92)00104-t schema:sameAs https://app.dimensions.ai/details/publication/pub.1004992278
    74 rdf:type schema:CreativeWork
    75 https://doi.org/10.1016/j.jsc.2005.11.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032968943
    76 rdf:type schema:CreativeWork
    77 https://doi.org/10.1080/00927870902828793 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012892446
    78 rdf:type schema:CreativeWork
    79 https://doi.org/10.1090/conm/377/06998 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089201463
    80 rdf:type schema:CreativeWork
    81 https://doi.org/10.1137/09075024x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062856031
    82 rdf:type schema:CreativeWork
    83 https://doi.org/10.1142/s0218196711006674 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062961627
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.4171/rmi/561 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072320881
    86 rdf:type schema:CreativeWork
    87 https://www.grid.ac/institutes/grid.35135.31 schema:alternateName Saint Petersburg Academic University
    88 schema:name St. Petersburg Academic University, St. Petersburg, Russia
    89 rdf:type schema:Organization
     




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


    ...