| Nama Pengarang | : | Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| Nama Majalah/Jurnal | : | Journal of the ACM |
| Volume / Nomor Edisi | : | 65 (No. 6) |
| Nomor Halaman | : | 1-40 |
| Abstraksi Narasi | : | n the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+?)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+?)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ?)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ?)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+?)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ?)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and M?dry [27]. These two new tools might be of independent interest. |
| Nama Pengarang | : | Wisnu Anggoro, Paulus,Ratnasari, Lucia |
| Nama Majalah/Jurnal | : | Jurnal Teknologi Industri |
| Volume / Nomor Edisi | : | 7 (No. 3) |
| Nomor Halaman | : | 211-222 |
| Abstraksi Narasi | : | It is impossible for an operator in practice to make components in ideal geometrical quality. Some deviations indeed can not be avoided during the process of components making. Hence, it is important for operator to use tolerance. However, in practice, Cost-International Tolerance (IT) Curve method does not always be used to determine the optimal geometrical tolerance, because of some limitations of the processing itself. Four important factors considered in the analysis of determining the length of components processing are the geometrical tolerance quality (IT), motor speed (n-rpm), feeding rate (s), and the operator. All factors are considered as an important variable in determining the quality of the components, which processed by conventional machine. In this research, some effects of giving geometrical tolerance as a function of processing time are studied by using Factorial Experiment Design. The results are summarized as follows: The four factors give a significant effect to the processing time |
| Nama Pengarang | : | - |
| Nama Majalah/Jurnal | : | Jurnal Teknologi Industri |
| Volume / Nomor Edisi | : | 7 (No. 3) |
| Nomor Halaman | : | 201-210 |
| Abstraksi Narasi | : | The recently developed multi resolution time-domain (MRTD) based on Haar wavelets is applied to the modeling of electromagnetic wave pulsation. The multi resolution nature of the wavelets was used in the formulation and a time stepping algorithm that is similar to the conventional finite difference time-domain (FDTD) method is discussed. Perfect electric conductor condition has been formulated and implemented. Computed electromagnetic fields are compared to the exact solution, the comparison shows a good agreement. |
| Nama Pengarang | : | Moshe Babaioff, Nicole Immorlica, David Kempe, Robert Kleinberg |
| Nama Majalah/Jurnal | : | Journal of the ACM |
| Volume / Nomor Edisi | : | 65 (No. 6) |
| Nomor Halaman | : | 1-26 |
| Abstraksi Narasi | : | We define a generalization of the classical secretary problem called the matroid secretary problem. In this problem, the elements of a matroid are presented to an online algorithm in uniformly random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. We present an O(log k)-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid. |
| Nama Pengarang | : | Dewi, Luciana Triana |
| Nama Majalah/Jurnal | : | Jurnal Teknologi Industri |
| Volume / Nomor Edisi | : | 7 (No. 3) |
| Nomor Halaman | : | 191-200 |
| Abstraksi Narasi | : | It is important to measure human's potential error in work system since human are essential in such system. Some human-performance reliability analysis methods had been developed. This paper explains four methods in human reliability analysis which are: Technique for Human Error rate Prediction (THERP), Human Error Assessment and Reduction Technique (HEART), Justification of Human Error Data Information (JHEDI), and Human Error and Criticality Analysis (HECA). The four methods are then compared to each other, and their use, strengths and weaknesses are identified. The result is useful in choosing the proper method for human reliability analysis of a system. |
| Nama Pengarang | : | Kusnadi |
| Nama Majalah/Jurnal | : | Jurnal Teknologi Industri |
| Volume / Nomor Edisi | : | 7 (No. 3) |
| Nomor Halaman | : | 179-190 |
| Abstraksi Narasi | : | Canonical Huffman coding is considered quite optimal for lossless compression; in the case that encoder can operate off-line. However, because generally canonical Huffman coding is bit-oriented, it is considered rather slow in term of decoding time. In this paper, byte-oriented scheme is employed to gain faster decoding with loss of some compression. Other fast non-entropy coders are also discussed for comparisons. |
| Nama Pengarang | : | B. Hanandoko, Theodorus,Rosmawati, Triana |
| Nama Majalah/Jurnal | : | Jurnal Teknologi Industri |
| Volume / Nomor Edisi | : | 7 (No. 3) |
| Nomor Halaman | : | 165-178 |
| Abstraksi Narasi | : | Sand casting technology has been known as metal processing without scraps. Practically, it is not easy to make cast products without defects. One of many factors considered in sand casting process is a shrinkage phenomenon. To provide better cast product, this phenomenon should be anticipated by good design in the shape and dimensions of pattern, sprue, and riser. This paper represents how to minimize defects in casting process by designing the pattern, sprue and riser for an Aluminum pulley with 3-inch diameter, which is usually used to transmit power by combining with the V-belt. |
| Nama Pengarang | : | Chandra Dewi K. |
| Nama Majalah/Jurnal | : | Jurnal Teknologi Industri |
| Volume / Nomor Edisi | : | 7 (No. 3) |
| Nomor Halaman | : | 155-164 |
| Abstraksi Narasi | : | In its application, Quality Function Deployment can fully relate engineering to marketing. This research tries to minimize Quality Function Deployment weakness by applying Integrated Concept Development method, to bridge the gap between engineering and marketing science. So that it can create market oriented development product concept. |
| Nama Pengarang | : | Hafsah,Ardanari, Patricia |
| Nama Majalah/Jurnal | : | Jurnal Teknologi Industri |
| Volume / Nomor Edisi | : | 7 (No. 3) |
| Nomor Halaman | : | 147-154 |
| Abstraksi Narasi | : | The emergence of the internet as the de facto global information infrastructure and the advances in networking and telecommunications have made a great number of information sources available on-line, especially on the web. The task of web information integration system is to answer queries that may require extracting and combining data from multiple web sources. Information integration system are based on a general architecture, where user interacts with a uniform interface in the form of a set virtual relation names that are used in formulating queries. The actual data is stored in external sources, called the source relations. In order for the system to be able to answer queries, we must specify a mapping between the virtual relations and the sources relations. The problem of answering queries using views has recently received significant attention because of its relevance to a wide variety of data management problems: query optimization, maintenance of physical data independence, data integration and data warehouse design. The Algorithms that can be derived from this theories are Bucket algorithm and Inverse-Rules algorithm. |
| Nama Pengarang | : | Sinaga, Benyamin L.,Wisnubhadra, Irya |
| Nama Majalah/Jurnal | : | Jurnal Teknologi Industri |
| Volume / Nomor Edisi | : | 7 (No. 2) |
| Nomor Halaman | : | 133-146 |
| Abstraksi Narasi | : | Software development is not free of error since software is the product of human work. For critical software such as the reactive system, software error constitutes a main priority to avoid. Automation of software development process from analysis phase to design phase, coding and testing is regarded as one way of avoiding the possibly happened error. This research is intended to build a ReactGen Software that could generate source code from analysis phase (state chart specification). State chart specification is chosen since it could describe the dynamic aspect of a reactive system completely. State chart specification is written using persistence object XML... The source code resulted from code generation would be free of error by applying software testing. ReactGen Software is built using Design patterns and Object Oriented Framework. |