GLORIA

GEOMAR Library Ocean Research Information Access

X

Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
  • 1
    Online Resource
    Online Resource
    Real-time scheduling to minimize machine busy times
    Springer Science and Business Media LLC ; 2015
    In:  Journal of Scheduling Vol. 18, No. 6 ( 2015-12), p. 561-573
    Details
    In: Journal of Scheduling, Springer Science and Business Media LLC, Vol. 18, No. 6 ( 2015-12), p. 561-573
    Type of Medium: Online Resource
    ISSN: 1094-6136 , 1099-1425
    URL: Article
    DOI: 10.1007/s10951-014-0411-z
    Language: English
    Publisher: Springer Science and Business Media LLC
    Publication Date: 2015
    detail.hit.zdb_id: 2012329-2
    SSG: 11
    SSG: 3,2
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 2
    Online Resource
    Online Resource
    Optimal multiple message broadcasting in telephone-like communication systems
    Elsevier BV ; 2000
    In:  Discrete Applied Mathematics Vol. 100, No. 1-2 ( 2000-03), p. 1-15
    Details
    In: Discrete Applied Mathematics, Elsevier BV, Vol. 100, No. 1-2 ( 2000-03), p. 1-15
    Type of Medium: Online Resource
    ISSN: 0166-218X
    URL: Article
    DOI: 10.1016/S0166-218X(99)00155-9
    Language: English
    Publisher: Elsevier BV
    Publication Date: 2000
    detail.hit.zdb_id: 1467965-6
    detail.hit.zdb_id: 804924-5
    detail.hit.zdb_id: 424010-8
    SSG: 17,1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 3
    Online Resource
    Online Resource
    On finding most uniform spanning trees
    Elsevier BV ; 1988
    In:  Discrete Applied Mathematics Vol. 20, No. 2 ( 1988-06), p. 173-175
    Details
    In: Discrete Applied Mathematics, Elsevier BV, Vol. 20, No. 2 ( 1988-06), p. 173-175
    Type of Medium: Online Resource
    ISSN: 0166-218X
    URL: Article
    DOI: 10.1016/0166-218X(88)90062-5
    Language: English
    Publisher: Elsevier BV
    Publication Date: 1988
    detail.hit.zdb_id: 1467965-6
    detail.hit.zdb_id: 804924-5
    detail.hit.zdb_id: 424010-8
    SSG: 17,1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 4
    Online Resource
    Online Resource
    A FAST PARALLEL ALGORITHM FOR FINDING THE CONVEX HULL OF A SORTED POINT SET
    World Scientific Pub Co Pte Ltd ; 1996
    In:  International Journal of Computational Geometry & Applications Vol. 06, No. 02 ( 1996-06), p. 231-241
    Details
    In: International Journal of Computational Geometry & Applications, World Scientific Pub Co Pte Ltd, Vol. 06, No. 02 ( 1996-06), p. 231-241
    Abstract: We present a parallel algorithm for finding the convex hull of a sorted point set. The algorithm runs in O( log log n) (doubly logarithmic) time using n/ log log n processors on a Common CRCW PRAM. To break the Ω( log n/ log log n) time barrier required to output the convex hull in a contiguous array, we introduce a novel data structure for representing the convex hull. The algorithm is optimal in two respects: (1) the time-processor product of the algorithm, which is linear, cannot be improved, and (2) the running time, which is doubly logarithmic, cannot be improved even by using a linear number of processors. The algorithm demonstrates the power of the “the divide-and-conquer doubly logarithmic paradigm” by presenting a non-trivial extension to situations that previously were known to have only slower algorithms.
    Type of Medium: Online Resource
    ISSN: 0218-1959 , 1793-6357
    URL: Article
    DOI: 10.1142/S0218195996000162
    Language: English
    Publisher: World Scientific Pub Co Pte Ltd
    Publication Date: 1996
    SSG: 11
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 5
    Online Resource
    Online Resource
    Minimizing Service and Operation Costs of Periodic Scheduling
    Institute for Operations Research and the Management Sciences (INFORMS) ; 2002
    In:  Mathematics of Operations Research Vol. 27, No. 3 ( 2002-08), p. 518-544
    Details
    In: Mathematics of Operations Research, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 27, No. 3 ( 2002-08), p. 518-544
    Abstract: We study the problem of scheduling activities of several types under the constraint that, at most, a fixed number of activities can be scheduled in any single time slot. Any given activity type is associated with a service cost and an operating cost that increases linearly with the number of time slots since the last service of this type. The problem is to find an optimal schedule that minimizes the long-run average cost per time slot. Applications of such a model are the scheduling of maintenance service to machines, multi-item replenishment of stock, and minimizing the mean response time in Broadcast Disks. Broadcast Disks recently gained a lot of attention because they were used to model backbone communications in wireless systems, Teletext systems, and Web caching in satellite systems. The first contribution of this paper is the definition of a general model that combines into one several important previous models. We prove that an optimal cyclic schedule for the general problem exists, and we establish the NP-hardness of the problem. Next, we formulate a nonlinear program that relaxes the optimal schedule and serves as a lower bound on the cost of an optimal schedule. We present an efficient algorithm for finding a near-optimal solution to the nonlinear program. We use this solution to obtain several approximation algorithms. (1) A 9/8 approximation for a variant of the problem that models the Broadcast Disks application. The algorithm uses some properties of “Fibonacci sequences.” Using this sequence, we present a 1.57-approximation algorithm for the general problem. (2) A simple randomized algorithm and a simple deterministic greedy algorithm for the problem. We prove that both achieve approximation factor of 2. To the best of our knowledge this is the first worst-case analysis of a widely used greedy heuristic for this problem.
    Type of Medium: Online Resource
    ISSN: 0364-765X , 1526-5471
    URL: Article
    DOI: 10.1287/moor.27.3.518.314
    Language: English
    Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
    Publication Date: 2002
    detail.hit.zdb_id: 2004273-5
    detail.hit.zdb_id: 195683-8
    SSG: 3,2
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 6
    Online Resource
    Online Resource
    Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
    Society for Industrial & Applied Mathematics (SIAM) ; 2000
    In:  SIAM Journal on Discrete Mathematics Vol. 13, No. 2 ( 2000-01), p. 255-267
    Details
    In: SIAM Journal on Discrete Mathematics, Society for Industrial & Applied Mathematics (SIAM), Vol. 13, No. 2 ( 2000-01), p. 255-267
    Type of Medium: Online Resource
    ISSN: 0895-4801 , 1095-7146
    URL: Article
    DOI: 10.1137/S0895480195291874
    RVK:
    SA 1075
    Language: English
    Publisher: Society for Industrial & Applied Mathematics (SIAM)
    Publication Date: 2000
    detail.hit.zdb_id: 1468404-4
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 7
    Online Resource
    Online Resource
    Buffer Overflow Management in QoS Switches
    Society for Industrial & Applied Mathematics (SIAM) ; 2004
    In:  SIAM Journal on Computing Vol. 33, No. 3 ( 2004-01), p. 563-583
    Details
    In: SIAM Journal on Computing, Society for Industrial & Applied Mathematics (SIAM), Vol. 33, No. 3 ( 2004-01), p. 563-583
    Type of Medium: Online Resource
    ISSN: 0097-5397 , 1095-7111
    URL: Article
    DOI: 10.1137/S0097539701399666
    RVK:
    SA 7990
    Language: English
    Publisher: Society for Industrial & Applied Mathematics (SIAM)
    Publication Date: 2004
    detail.hit.zdb_id: 1383550-6
    detail.hit.zdb_id: 185851-8
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 8
    Online Resource
    Online Resource
    A lower bound for integer greatest common divisor computations
    Association for Computing Machinery (ACM) ; 1991
    In:  Journal of the ACM Vol. 38, No. 2 ( 1991-04), p. 453-471
    Details
    In: Journal of the ACM, Association for Computing Machinery (ACM), Vol. 38, No. 2 ( 1991-04), p. 453-471
    Abstract: It is proved that no finite computation tree with operations { +, -, *, /, mod, 〈 } can decide whether the greatest common divisor (gcd) of a and b is one, for all pairs of integers a and b . This settles a problem posed by Gro¨tschel et al. Moreover, if the constants explicitly involved in any operation performed in the tree are restricted to be “0” and “1” (and any other constant must be computed), then we prove an Ω(log log n ) lower bound on the depth of any computation tree with operations { +, -, *, /, mod, 〈 } that decides whether the gcd of a and b is one, for all pairs of n -bit integers a and b . A novel technique for handling the truncation operation is implicit in the proof of this lower bound. In a companion paper, other lower bounds for a large class of problems are proved using a similar technique.
    Type of Medium: Online Resource
    ISSN: 0004-5411 , 1557-735X
    URL: Article
    DOI: 10.1145/103516.103522
    RVK:
    SA 3010
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 1991
    detail.hit.zdb_id: 2006500-0
    detail.hit.zdb_id: 6759-3
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 9
    Online Resource
    Online Resource
    Divide-and-conquer approximation algorithms via spreading metrics
    Association for Computing Machinery (ACM) ; 2000
    In:  Journal of the ACM Vol. 47, No. 4 ( 2000-07), p. 585-616
    Details
    In: Journal of the ACM, Association for Computing Machinery (ACM), Vol. 47, No. 4 ( 2000-07), p. 585-616
    Abstract: We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns lengths to either edges or vertices of the input graph, such that all subgraphs for which the optimization problem is nontrivial have large diameters. In addition, the spreading metric provides a lower bound, τ, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modeled by our paradigm whose approximation factor is O (min{log τ, log log τ, log k log log k }) where k denotes the number of “interesting” vertices in the problem instance, and is at most the number of vertices. We present seven problems that can be formulated to fit the paradigm. For all these problems our algorithm improves previous results. The problems are: (1) linear arrangement; (2) embedding a graph in a d -dimensional mesh; (3) interval graph completion; (4) minimizing storage-time product; (5) subset feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks; (7) balanced partitions and p -separators (for small values of p ) in directed graphs.
    Type of Medium: Online Resource
    ISSN: 0004-5411 , 1557-735X
    URL: Article
    DOI: 10.1145/347476.347478
    RVK:
    SA 3010
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2000
    detail.hit.zdb_id: 2006500-0
    detail.hit.zdb_id: 6759-3
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 10
    Online Resource
    Online Resource
    Efficient routing in optical networks
    Association for Computing Machinery (ACM) ; 1996
    In:  Journal of the ACM Vol. 43, No. 6 ( 1996-11), p. 973-1001
    Details
    In: Journal of the ACM, Association for Computing Machinery (ACM), Vol. 43, No. 6 ( 1996-11), p. 973-1001
    Abstract: This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into several channels, each at a different optical wavelength. A connection between two nodes is assigned a specific wavelength, with the constraint that no two connections sharing a link in the network can be assigned the same wavelength. This paper considers optical networks with and without switches, and different types of routing in these networks. It presents optimal or near-optimal constructions of optical networks in these cases and algorithms for routing connections, specifically permutation routing for the networks constructed here.
    Type of Medium: Online Resource
    ISSN: 0004-5411 , 1557-735X
    URL: Article
    DOI: 10.1145/235809.235812
    RVK:
    SA 3010
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 1996
    detail.hit.zdb_id: 2006500-0
    detail.hit.zdb_id: 6759-3
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...