Library

X
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
    Packings in two dimensions: Asymptotic average-case analysis of algorithms (1993)
    Springer
    Algorithmica 9 (1993), S. 253-277 
    Details
    ISSN: 1432-0541
    Keywords: Average-case analysis ; Cutting stock problems ; Two-dimensional packing ; Bin packing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract New approximation algorithms for packing rectangles into a semi-infinite strip are introduced in this paper. Within a standard probability model, an asymptotic average-case analysis is given for the wasted space in the packings produced by these algorithms. An off-line algorithm is presented along with a proof that it wastes θ(√/n)space on the average, wheren is the number of rectangles packed. This result is known to apply to optimal packings as well. Several on-line shelf algorithms are also analyzed. Withn assumed known in advance, one such algorithm is described and shown to waste θ(n 2/3) space on the average. It is proved that this result also characterizes optimal on-line shelf packings. For a very general class of linear-time algorithms, it is shown that a constant (nonzero) fraction of the space must be wasted on the average for alln, and a lower bound on this fraction in terms of algorithm parameters is given. Finally, the paper discusses the implications of the above results for dynamic packing and two-dimensional bin-packing problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190899
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Packing random intervals (1995)
    Springer
    Probability theory and related fields 102 (1995), S. 105-121 
    Details
    ISSN: 1432-2064
    Keywords: 60D05 ; 05B40 ; 52A22
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Letn random intervalsI 1, ...,I n be chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this “best” packing has wasted space $$O(\frac{{\log ^2 n}}{n})$$ . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01295224
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    An efficient algorithm for allocating paged, drum-like storage (1978)
    Springer
    BIT 18 (1978), S. 52-66 
    Details
    ISSN: 1572-9125
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Cody and Coffman have studied the problem of distributing a set of a equal-size records among the sectors of a drum-like storage device so as to minimize the average rotational latency cost. This paper is an extension of that work. We employ the same model but a different latency delay function. Motivated by the NP-completeness of the general problem and the fact that an arbitrary assignment can have an expected latency cost almost twice that of an optimal assignment, we propose and analyze a fast heuristic whose performance compares favorably with that of an optimal algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01947743
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Batch sizing and job sequencing on a single machine (1990)
    Springer
    Annals of operations research 26 (1990), S. 135-147 
    Details
    ISSN: 1572-9338
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02248589
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Queueing models of secondary storage devices (1986)
    Springer
    Queueing systems 1 (1986), S. 129-168 
    Details
    ISSN: 1572-9443
    Keywords: Computer storage devices ; auxiliary storage systems ; queueing analyses of computer secondary storage ; stochastic models of computer auxiliary memory systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Queueing theory has occupied an important role in the analysis of computer storage structures and algorithms. In this survey we focus on secondary or auxiliary storage devices, which often comprise the principal bottleneck in the overall performance of computer systems. We begin with descriptions of the more important devices, such as disks and drums, and a general discussion of related queueing models. Server motion and dependent successive services are salient features of these models. Widely used, generic results are presented and then applied to specific devices. The paper concludes with a discussion of open problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01536186
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Polling and greedy servers on a line (1987)
    Springer
    Queueing systems 2 (1987), S. 115-145 
    Details
    ISSN: 1572-9443
    Keywords: Polling systems ; disk systems ; disk SCAN policy ; shortest-seek-time-first disk scheduling ; moving-server systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A single server moves with speed υ on a line interval (or a circle) of length (circumference)L. Customers, requiring service of constant durationb, arrive on the interval (or circle) at random at mean rate λ customers per unit length per unit time. A customer's mean wait for service depends partly on the rules governing the server's motion. We compare two different servers: thepolling server and thegreedy server. Without knowing the locations of waiting customers, a polling server scans endlessly back and forth across the interval (or clockwise around the circle), stopping only where it encounters a waiting customer. Knowing where customers are waiting, a greedy server always travels toward the current nearest one. Except for certain extreme values of υ,L, b, andλ, the polling and greedy servers are roughly equally effective. Indeed, the simpler polling server is often the better. Theoretical results show, in most cases, that the polling server has a high probability of moving toward the nearest customer, i.e. moving as a greedy server would. The greedy server is difficult to analyze, but was simulated on a computer.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01158396
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    On file structuring for non-uniform access frequencies (1970)
    Springer
    BIT 10 (1970), S. 443-456 
    Details
    ISSN: 1572-9125
    Keywords: Dewey (17th): 651.8 ; U.D.C.: 007 681.322.025 ; Trees ; search Structures ; data ; file ; tree Information Retrieval
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An important property of file structures is their behavior when the underlying distribution of access frequencies is non-uniform. In this note we consider methods for structuring files so that initially unknown but non-uniform access frequencies are exploited in a way that reduces mean search times. As a specific illustration a simple algorithm is applied to sequence search trees and shown to produce structures with mean search times that are significantly less than those produced by an algorithm creating tree structures independent of access frequencies. An analytic result is obtained for this improvement when access frequencies are uniform. Samples from the results of Monte Carlo simulations are used to illustrate this improvement when access frequencies are non-uniform.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01935564
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Performance predictions for extended paged memories (1971)
    Springer
    Acta informatica 1 (1971), S. 1-13 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary This paper concerns the problem of obtaining predictions of the extent to which additional core storage would improve the performance of a given paging system based on information that could be obtained from monitoring the system whilst running its normal workload. It is shown that for a large class of replacement algorithms there are efficient techniques for producing exact predictions of the performance improvement, and that for a further class of algorithms statistical predictions can be provided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00264288
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Optimal scheduling for two-processor systems (1972)
    Springer
    Acta informatica 1 (1972), S. 200-213 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Despite the recognized potential of multiprocessing little is known concerning the general problem of finding efficient algorithms which compute minimallength schedules for given computations and m≧2 processors. In this paper we formulate a general model of computation structures and exhibit an efficient algorithm for finding optimal nonpreemptive schedules for these structures on two-processor systems. We prove that the algorithm gives optimal solutions and discuss its application to preemptive scheduling disciplines.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00288685
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Scheduling saves in fault-tolerant computations (1993)
    Springer
    Acta informatica 30 (1993), S. 409-423 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Computer users with very long computations run the risk of losing work because of machine failures. Such losses can often be reduced by scheduling saves on secure storage devices of work successfully done. In the model studied here, the user leaves the computation unattended for extended periods of time, after which he or she returns to check whether a machine failure occurs. When a check reveals a failure, the user resets the computation so that it resumes from the point of the last successful save. Saves are themselves time consuming, so that any strategy for scheduling saves must strike a balance between the computing time lost during saves and the computing time that is occasionally lost, because of a failure since the last successful save. For a given time to the next check and given constant save times, this paper computes schedules that maximize the expected amount of work successfully done before the next check, under the uniform and exponential failure laws. Explicit formulas are obtained for the uniform law. A recurrence leads to routine numerical calculations for the more difficult system with an exponential failure law.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01210593
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...