Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 46 (1990), S. 153-171 
    ISSN: 1436-4646
    Keywords: Spanning networks ; two-connectivity ; traveling salesman problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the problem of constructing a minimum-weight, two-connected network spanning all the points in a setV. We assume a symmetric, nonnegative distance functiond(·) defined onV × V which satisfies the triangle inequality. We obtain a structural characterization of optimal solutions. Specifically, there exists an optimal two-connected solution whose vertices all have degree 2 or 3, and such that the removal of any edge or pair of edges leaves a bridge in the resulting connected components. These are the strongest possible conditions on the structure of an optimal solution since we also show thatany two-connected graph satisfying these conditions is theunique optimal solution for a particular choice of ‘canonical’ distances satisfying the triangle inequality. We use these properties to show that the weight of an optimal traveling salesman cycle is at most 4/3 times the weight of an optimal two-connected solution; examples are provided which approach this bound arbitrarily closely. In addition, we obtain similar results for the variation of this problem where the network need only span a prespecified subset of the points.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 68 (1995), S. 241-265 
    ISSN: 1436-4646
    Keywords: Asymmetric traveling salesman problem ; Precedence constraints ; Facets ; Generalized TSP
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Many applications of the traveling salesman problem require the introduction of additional constraints. One of the most frequently occurring classes of such constraints are those requiring that certain cities be visited before others (precedence constraints). In this paper we study the Precedence-Constrained Asymmetric Traveling Salesman (PCATS) polytope, i.e. the convex hull of incidence vectors of tours in a precedence-constrained directed graph. We derive several families of valid inequalities, and give polynomial time separation algorithms for important subfamilies. We then establish the dimension of the PCATS polytope and show that, under reasonable assumptions, the two main classes of inequalities derived are facet inducing.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Graphs and combinatorics 5 (1989), S. 15-28 
    ISSN: 1435-5914
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Ac-hybrid triple system of orderv is a decomposition of the completev-vertex digraph intoc cyclic tournaments of order 3 and $$\frac{{v(v - 1)}}{3} - c$$ transitive tournaments of order 3. Hybrid triple systems generalize directed triple systems (c = 0) and Mendelsohn triple systems (c = v(v − 1)/3); omitting directions yields an underlying twofold triple system. The spectrum ofv andc for which ac-hybrid triple system of orderv exists is completely determined in this paper. Using (cubic) block intersection graphs, we then show that every twofold triple system of order $$v\left( {having b_v = \frac{{v(v - 1)}}{3}blocks} \right)$$ underlies ac-hybrid triple system with $$c \geqslant \frac{{2b_v }}{3}$$ . Examples are constructed for all sufficiently largev, for which this maximum is at most $$\left( {\frac{7}{{10}} + \varepsilon } \right)b_v $$ . The lower bound here is proved by establishing bounds onF i (n, r), the size of minimum cardinality vertex feedback sets inn-vertexi-connected cubic multigraphs havingr repeated edges. We establish that $$F_0 (n,r) \leqslant \frac{n}{2},$$ , $$F_1 (n,r) \leqslant \frac{{3n}}{8} + \frac{r}{4} + \frac{1}{2}, and F_2 (n,r) \leqslant \frac{{(n + r)}}{3}for n 〉 8$$ . These bounds are all tight, and the latter is used to derive the lower bound in the design theoretic problem.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Order 1 (1985), S. 225-229 
    ISSN: 1572-9273
    Keywords: Primary 06A10 ; secondary 05C99, 68E99 ; ordered set ; jump number ; width ; setup number ; polynomial time algorithm ; dynamic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A simply polynomial time algorithm is given for computing the setup number, or jump number, of an ordered set with fixed width. This arises as an interesting application of a polynomial time algorithm for solving a more general weighted problem in precedence constrained scheduling.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 76 (1998), S. 0-0 
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The goal of the series "Mathematics of Industrial Systems" (MIS) is to describe and promote the role of applied mathematics in industrial systems. In particular, the publication focuses on discrete models and combinatorial solution approaches in industry, where the term industry should be understood in a broad sense.The third volume of this series contains fourteen contributions. The papers describe successful applications of mathematics to applied problems and propose new solution procedures. Two papers deal with interesting applications in telecommunication, namely network synthesis problems and frequency assignment for cellular phone networks. Further articles describe an efficient routing of helicopters for crew exchange, stowage planning for container ships, and mathematical tools in airline schedule planning. Several papers deal with aspects of production processes, starting from dynamic facility layout and the design and operation of AGV-served manufacturing systems, via matching of assembly operations, material planning and tool allocation to certain aspects of scheduling problems.Many people have helped in the preparation of this third volume of MIS. In particular, we would like to thank the referees for their careful work and thoughtful remarks. Their efforts substantially improved the quality of this volume. Moreover, our appreciation is due to Mrs. Nelly Segal, RUTCOR, for providing much help to the editors and for handling editorial matters in such an excellent way.The fourth volume of this series is already in preparation. Submissions for this or another forthcoming volume in the series can be sent to any of the editors. Moreover, comments and proposals for future volumes are welcome and appreciated by the editors.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Title: Mathematics of industrial systems III; 76
    Contributer: Burkard, Rainer E. , Ibaraki, Toshihide , Pulleyblank, William R.
    Publisher: Amsterdam :Baltzer Science Publ.,
    Year of publication: 1998
    Pages: 344 S.
    Series Statement: Annals of operations research 76
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 7
    Title: Combinatorial optimization
    Author: Cook, William J.
    Contributer: Cunningham, William H. , Pulleyblank, William R. , Schrijver, Alexander
    Publisher: New York u.a. :Wiley,
    Year of publication: 1998
    Pages: 355 S.
    Series Statement: Wiley interscience series in discrete mathematics and optimization
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 8
    Publication Date: 2014-02-24
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 9
    Publication Date: 2014-02-24
    Language: English
    Type: article , doc-type:article
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...