SwePub
Sök i LIBRIS databas

  Utökad sökning

WFRF:(Krupke Dominik)
 

Sökning: WFRF:(Krupke Dominik) > Computing Nonsimple...

LIBRIS Formathandbok  (Information om MARC21)
FältnamnIndikatorerMetadata
00003546naa a2200433 4500
001oai:DiVA.org:liu-132697
003SwePub
008161118s2016 | |||||||||||000 ||eng|
0247 a https://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-1326972 URI
0247 a https://doi.org/10.1007/978-3-319-38851-9_102 DOI
040 a (SwePub)liu
041 a engb eng
042 9 SwePub
072 7a ref2 swepub-contenttype
072 7a kon2 swepub-publicationtype
1001 a Fekete, Sandor P.u TU Braunschweig, Germany4 aut
2451 0a Computing Nonsimple Polygons of Minimum Perimeter
264 c 2016-06-01
264 1a Cham :b SPRINGER INT PUBLISHING AG,c 2016
338 a print2 rdacarrier
520 a We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertices in the plane, the problem Minimum Perimeter Polygon (MPP) asks for a (not necessarily simply connected) polygon with shortest possible boundary length. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MPP. On the positive side, we show how to achieve a constant-factor approximation. When trying to solve MPP instances to provable optimality by means of integer programming, an additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting additional geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that using a natural geometry-based sparsification yields results that are on average within 0.5% of the optimum.
650 7a NATURVETENSKAPx Matematikx Diskret matematik0 (SwePub)101042 hsv//swe
650 7a NATURAL SCIENCESx Mathematicsx Discrete Mathematics0 (SwePub)101042 hsv//eng
653 a Traveling Salesman Problem (TSP); Minimum Perimeter Polygon (MPP); Curve reconstruction; NP-hardness; Exact optimization; Integer programming; Computational geometry meets combinatorial optimization
7001 a Haas, Andreasu TU Braunschweig, Germany4 aut
7001 a Hemmer, Michaelu TU Braunschweig, Germany4 aut
7001 a Hoffmann, Michaelu Swiss Federal Institute Technology, Switzerland4 aut
7001 a Kostitsyna, Irinau TU Eindhoven, Netherlands4 aut
7001 a Krupke, Dominiku TU Braunschweig, Germany4 aut
7001 a Maurer, Florianu TU Braunschweig, Germany4 aut
7001 a Mitchell, Joseph S. B.u SUNY Stony Brook, NY 11794 USA4 aut
7001 a Schmidt, Arneu TU Braunschweig, Germany4 aut
7001 a Schmidt, Christianeu Linköpings universitet,Kommunikations- och transportsystem,Tekniska fakulteten4 aut0 (Swepub:liu)chrsc91
7001 a Troegel, Julianu TU Braunschweig, Germany4 aut
7102 a TU Braunschweig, Germanyb Swiss Federal Institute Technology, Switzerland4 org
7730 t EXPERIMENTAL ALGORITHMS, SEA 2016d Cham : SPRINGER INT PUBLISHING AGg , s. 134-149q <134-149z 9783319388502z 9783319388519
8564 u https://www.research-collection.ethz.ch/bitstream/20.500.11850/229763/2/303-1406-1-PB.pdf
8564 8u https://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-132697
8564 8u https://doi.org/10.1007/978-3-319-38851-9_10

Hitta via bibliotek

Till lärosätets databas

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy