Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint
49
0
0.0
(
0
)
Added by
Kai Wang
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Authors
G. Calinescu
Ask ChatGPT about the research
No Arabic abstract
In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be scheduled at a specified position. We give dynamic programs with pseudo-polynomial running time, and a fully polynomial-time approximation scheme (FPTAS).
rate research
Read More
We give a 1.488-approximation for the classic scheduling problem of minimizing total weighted completion time on unrelated machines. This is a considerable improvement on the recent breakthrough of $(1.5 - 10^{-7})$-approximation (STOC 2016, Bansal-Srinivasan-Svensson) and the follow-up result of $(1.5 - 1/6000)$-approximation (FOCS 2017, Li). Bansal et al. introduced a novel rounding scheme yielding strong negative correlations for the first time and applied it to the scheduling problem to obtain their breakthrough, which resolved the open problem if one can beat out the long-standing $1.5$-approximation barrier based on independent rounding. Our key technical contribution is in achieving significantly stronger negative correlations via iterative fair contention resolution, which is of independent interest. Previously, Bansal et al. obtained strong negative correlations via a variant of pipage type rounding and Li used it as a black box.
In this paper, we study the stochastic unbounded min-knapsack problem ($textbf{Min-SUKP}$). The ordinary unbounded min-knapsack problem states that: There are $n$ types of items, and there is an infinite number of items of each type. The items of the same type have the same cost and weight. We want to choose a set of items such that the total weight is at least $W$ and the total cost is minimized. The prob~generalizes the ordinary unbounded min-knapsack problem to the stochastic setting, where the weight of each item is a random variable following a known distribution and the items of the same type follow the same weight distribution. In prob, different types of items may have different cost and weight distributions. In this paper, we provide an FPTAS for $textbf{Min-SUKP}$, i.e., the approximate value our algorithm computes is at most $(1+epsilon)$ times the optimum, and our algorithm runs in $poly(1/epsilon,n,log W)$ time.
New optical technologies offer the ability to reconfigure network topologies dynamically, rather than setting them once and for all. This is true in both optical wide area networks (optical WANs) and in datacenters, despite the many differences between these two settings. Because of these new technologies, there has been a surge of both practical and theoretical research on algorithms to take advantage of them. In particular, Jia et al. [INFOCOM 17] designed online scheduling algorithms for dynamically reconfigurable topologies for both the makespan and sum of completion times objectives. In this paper, we work in the same setting but study an objective that is more meaningful in an online setting: the sum of flow times. The flow time of a job is the total amount of time that it spends in the system, which may be considerably smaller than its completion time if it is released late. We provide competitive algorithms for the online setting with speed augmentation, and also give a lower bound proving that speed augmentation is in fact necessary. As a side effect of our techniques, we also improve and generalize the results of Jia et al. on completion times by giving an $O(1)$-competitive algorithm for arbitrary sizes and release times even when nodes have different degree bounds, and moreover allow for the weighted sum of completion times (or flow times).
A non-invasive, in-situ calibration method for Total Internal Reflection Microscopy (TIRM) based on optical tweezing is presented which greatly expands the capabilities of this technique. We show that by making only simple modifications to the basic TIRM sensing setup and procedure, a probe particles absolute position relative to a dielectric interface may be known with better than 10 nm precision out to a distance greater than 1 $mu$m from the surface. This represents an approximate 10x improvement in error and 3x improvement in measurement range over conventional TIRM methods. The techniques advantage is in the direct measurement of the probe particles scattering intensity vs. height profile in-situ, rather than relying on calculations or inexact system analogs for calibration. To demonstrate the improved versatility of the TIRM method in terms of tunability, precision, and range, we show our results for the hindered near-wall diffusion coefficient for a spherical dielectric particle.
We report an experiment in which two-photon interference occurs between degenerate single photons that never meet. The two photons travel in opposite directions through our fibre-optic interferometer and interference occurs when the photons reach two different, spatially separated, 2-by-2 couplers at the same time. We show that this experiment is analogous to the conventional Franson-type entanglement experiment where the photons are entangled in position and time. We measure wavefunction overlaps for the two photons as high as 94 $pm$ 3%.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
