201 research outputs found
An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio
No full textThe problem of sorting with priced information was introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparisons have different (potentially infinite) costs. The goal is to find a sorting algorithm with small competitive ratio, defined as the (worst-case) ratio of the algorithm’s cost to the cost of the cheapest proof of the sorted order. The simple case of bichromatic sorting posed by [CFGKRS] remains open: We are given two sets A and B of total size N, and the cost of an A-A comparison or a B-B comparison is higher than an A-B comparison. The goal is to sort A ∪ B. An Ω(log N) lower bound on competitive ratio follows from unit-cost sorting. Note that this is a generalization of the famous nuts and bolts problem, where A-A and B-B comparisons have infinite cost, and elements of A and B are guaranteed to alternate in the final sorted order. In this paper we give a randomized algorithm InversionSort with an almost-optimal w.h.p. competitive ratio of O(log³ N). This is the first algorithm for bichromatic sorting with a o(N) competitive ratio.<br/
On Instance-Optimal Algorithms for a Generalization of Nuts and Bolts and Generalized Sorting
No full textWe generalize the classical nuts and bolts problem to a setting where the input is a collection of n nuts and m bolts, and there is no promise of any matching pairs. It is not allowed to compare a nut directly with a nut or a bolt directly with a bolt, and the goal is to perform the fewest nut-bolt comparisons to discover the partial order between the nuts and bolts. We term this problem bipartite sorting. We show that instances of bipartite sorting of the same size exhibit a wide range of complexity, and propose to perform a fine-grained analysis for this problem. We rule out straightforward notions of instance-optimality as being too stringent, and adopt a neighborhood-based definition. Our definition may be of independent interest as a unifying lens for instance-optimal algorithms for other static problems existing in literature. This includes problems like sorting (Estivill-Castro and Woods, ACM Comput. Surv. 1992), convex hull (Afshani, Barbay and Chan, JACM 2017), adaptive joins (Demaine, López-Ortiz and Munro, SODA 2000), and the recent concept of universal optimality for graphs (Haeupler, Hladík, Rozhoň, Tarjan and Tětek, 2023). As our main result on bipartite sorting, we give a randomized algorithm that is within a factor of O(log³(n+m)) of being instance-optimal w.h.p., with respect to the neighborhood-based definition. As our second contribution, we generalize bipartite sorting to DAG sorting, when the underlying DAG is not necessarily bipartite. As an unexpected consequence of a simple algorithm for DAG sorting, we rule out a potential lower bound on the widely-studied problem of sorting with priced information, posed by (Charikar, Fagin, Guruswami, Kleinberg, Raghavan and Sahai, STOC 2000). In this problem, comparing keys i and j has a known cost c_{ij} ∈ ℝ^+ ∪ {∞}, and the goal is to sort the keys in an instance-optimal way, by keeping the total cost of an algorithm as close as possible to ∑_{i=1}^{n-1} c_{x(i)x(i+1)}. Here x(1) < ⋯ < x(n) is the sorted order. While several special cases of cost functions have received a lot of attention in the community, no progress on the general version with arbitrary costs has been reported so far. One reason for this lack of progress seems to be a widely-cited Ω(n) lower bound on the competitive ratio for finding the maximum. This Ω(n) lower bound by (Gupta and Kumar, FOCS 2000) uses costs in {0,1,n, ∞}, and although not extended to sorting, this barrier seems to have stalled any progress on the general cost case. We rule out such a potential lower bound by showing the existence of an algorithm with a Õ(n^{3/4}) competitive ratio for the {0,1,n,∞} cost version. This generalizes the setting of generalized sorting proposed by (Huang, Kannan and Khanna, FOCS 2011), where the costs are either 1 or infinity, and the cost of the cheapest proof is always n-1.<br/
ATMOS 2006 Abstracts Collection -- Presentations at the 6th Workshop on Algorithmic Methods and Models for Optimization of Railways
No full textThe 6th Workshop on Algorithmic Methods and Models for Optimization of
Railways (ATMOS 06) is held
on September 14, 2006 in Zürich, Switzerland
(http://algo06.inf.ethz.ch/atmos), as part of the ALGO meeting
ATMOS 2006 Preface -- Algorithmic Methods and Models for Optimization of Railways
No full textThe 6th Workshop on Algorithmic Methods and Models for Optimization
of Railways (ATMOS 06) is held on September 14, 2006 in Z{\"u}rich, Switzerland
(http://algo06.inf.ethz.ch/atmos), as part of the ALGO meeting
External memory priority queues with decrease-key and applications to graph algorithms
No full textWe present priority queues in the external memory model with block size B and main memory size M that support on N elements, operation Update (a combination of operations Insert and DecreaseKey) in (Formula presented.) amortized I/Os and operations ExtractMin and Delete in (Formula presented.) amortized I/Os, for any real ε ∈ (0, 1), using (Formula presented.) blocks. Previous I/O-efficient priority queues either support these operations in (Formula presented.) amortized I/Os [Kumar and Schwabe, SPDP’96] or support only operations Insert, Delete and ExtractMin in optimal (Formula presented.) amortized I/Os, however without supporting DecreaseKey [Fadel et al., TCS’99]. We also present buffered repository trees that support on a multi-set of N elements, operation Insert in (Formula presented.) I/Os and operation Extract on K extracted elements in (Formula presented.) amortized I/Os, using O (N/B ) blocks. Previous results achieve (Formula presented.) B I/Os and (Formula presented.) I/Os, respectively [Buchsbaum et al., SODA’00]. Our results imply improved (Formula presented.) I/Os for single-source shortest paths, depth-first search and breadth-first search algorithms on massive directed dense graphs (V, E) with E = Ω (V 1+ε) , ε > 0 and V = Ω (M), which is equal to the I/O-optimal bound for sorting E values in external memory
An Optimal Randomized Algorithm for Finding the Saddlepoint
No full textA saddlepoint of an n × n matrix is an entry that is the maximum of its row and the minimum of its column. Saddlepoints give the value of a two-player zero-sum game, corresponding to its pure-strategy Nash equilibria; efficiently finding a saddlepoint is thus a natural and fundamental algorithmic task. For finding a strict saddlepoint (an entry that is the strict maximum of its row and the strict minimum of its column) an O(n log∗ n)-time algorithm was recently obtained by Dallant, Haagensen, Jacob, Kozma, and Wild, improving the O(n log n) bounds from 1991 of Bienstock, Chung, Fredman, Schäffer, Shor, Suri and of Byrne and Vaserstein. In this paper we present an optimal O(n)-time algorithm for finding a strict saddlepoint based on random sampling. Our algorithm, like earlier approaches, accesses matrix entries only via unit-cost binary comparisons. For finding a (non-strict) saddlepoint, we extend an existing lower bound to randomized algorithms, showing that the trivial O(n2) runtime cannot be improved even with the use of randomness
Unplugging Dijkstra’s Algorithm as a Mechanical Device
No full textGraphs are a fundamental concept in computer science, effectively modeling diverse scenarios such as social networks, protein interactions, and mobility. Dijkstra’s algorithm is crucial for computing single-source shortest path in graphs and is a key component of graph processing. This paper presents an educational activity designed to “unplug” graphs and Dijkstra’s algorithm, making these topics accessible to a broad audience. The activity utilizes a physical graph with chains as edges and key rings with retractable badge holders as nodes. By pulling two nodes of this graph apart, it is possible to find a shortest path between these nodes. This can be used to visualize how Dijkstra’s algorithm works, including how the graph models the world. It invites for discussing how much more efficient this is compared to enumerating all paths, and what additional insights computer scientists had to achieve impressive speedups over plain Dijkstra, allowing for route planning to be perceived as a solved problem, where we use the packaged solution without further thought. We discuss the implementation of this activity in public outreach events, such as Culture Nights and primary school classrooms
11. Multistage Methods for Freight Train Classification
No full textIn this paper we establish a consistent encoding of freight train classification methods.
This encoding scheme presents a powerful tool for efficient presentation and analysis of classification methods, which we successfully apply to illustrate the most relevant historic results from a more theoretical point of view.
We analyze their performance precisely and develop new classification methods making use of the inherent optimality condition of the encoding.
We conclude with deriving optimal algorithms and complexity results for restricted real-world settings
ANALISIS ISI PESAN EDUKASI SERIAL ANIMASI “RIKO THE SERIES” SEBAGAI NILAI KARAKTER PEDULI SOSIAL ANAK USIA DINI
No full textTechnological advances are currently developing very rapidly, especially in the fields of communication and information. Many people still don't realize that there are many social media that provide educational content for teaching materials. YouTube is one of the social media that has become a learning tool, one of which is the YouTube channel Riko The Series. In the animated series Riko The Series there are also several educational messages contained in it, one of which is the Character Value of Social Care. The research method used is a type of discourse analysis research developed by Teun A. Van Dijk, with a qualitative descriptive approach. Researchers will examine the content of educational messages in the animated series Riko The Series which contain social caring character values using Teun A. Van Dijk's discourse analysis model, namely in Episodes 1, 2, 3, 8, and 15. The results of the research and discussion can be drawn conclusions Overall, in Episodes 1, 2, 3, 8, 15 there are social care character values consisting of: a). Help, b). Apologize to each other, c). Caring for Others, d). Remind each other, e). Forgive. Through Teun A. Van Dijk's discourse strategy model, the author finds that the information in each sentence contained in the dialogue of the animated series "Riko The Series" is related to the information in other sentences, and has elements of coherence in it, so that a discourse structure is formed in the form of form and meaning. The characterization also seems to have a strong character. Teun A. Van Dijk's discourse analysis also captured information that the animation "Riko The Series" is one of the animations that has a socially caring character in accordance with the development of social attitudes in early childhood.Kemajuan teknologi saat ini berkembang dengan sangat pesat terutama pada bidang komunikasi dan informasi. Banyak orang yang masih belum menyadari banyak media sosial yang menyajikan konten edukasi untuk bahan pengajaran. Youtube menjadi salah satu media sosial yang sudah menjadi sarana pembelajaran, salah satunya channel Youtube Riko The Series. Pada serial animasi Riko The Series juga terdapat beberapa pesan Edukasi yang terkandung di dalamnya, salah satunya ialah Nilai Karakter Peduli Sosial. Metode penelitian yang digunakan adalah jenis penelitian analisis wacana yang dikembangkan oleh Teun A. Van Dijk, dengan pendekatan deskriptif kualitatif. Peneliti akan meneliti isi pesan Edukasi pada Serial Animasi Riko The Series yang terdapat nilai karakter peduli sosial dengan menggunakan model analisis wacana Teun A. Van Dijk yaitu pada Episode 1,2,3,8, dan 15. Hasil penelitian dan pembahasan dapat ditarik kesimpulan secara keseluruhan bahwa pada Episode 1,2,3,8, 15 terdapat nilai karakter peduli sosial yang terdiri atas : a). Tolong-Menolong, b). Saling Meminta Maaf, c). Peduli Sesama, d). Saling Mengingatkan, e). Memaafkan. Melalui strategi wacana model Teun A. Van Dijk, penulis menemukan bahwa, informasi dalam setiap kalimat yang terdapat dalam dialog serial animasi "Riko The Series" berhubungan dengan informasi dalam kalimat lainnya, serta memiliki unsur-unsur koherensi di dalamnya, sehingga terbentuklah struktur wacana berupa bentuk dan makna. Penokohannya juga terlihat memiliki karakter yang kuat. Analisis wacana Teun A. Van Dijk juga menangkap informasi bahwa, animasi "Riko The Series" merupakan salah satu animasi yang memiliki karakter peduli sosial sesuai dengan perkembangan sikap sosial anak usia dini
- …
