We investigate the two-median problem on an M ×N mesh (M >= N) with a Manhattan (L1) metric and derive efficient algorithms w. r. t. m, n and r, the number of columns, rows and vertices in the mesh, respectively, that contain requests. Specifically, we give an algorithm with running times O(mn2 logm) in general (m >= n). For uniform meshes, we give an O(MN2) algorithm and an algorithm running in O(MN logN) time with high probability assuming the weights are i. i. d. random variables satisfying certain natural conditions. These improve upon the previously best known algorithm which ran in O(mn2 q) time where only unit requests were allowed and q was the total units of request.
Queues that temporarily store fixed-length packets are ubiquitous in network switches. Scheduling algorithms that prevents packet-loss are always desirable. Longest-Queue-First (LQF) is an on-line greedy algorithm widely exploited because of its simplicity and efficiency. In this paper, we give improved bounds on the competitive ratio of LQF in terms of the worst-case queuing length, parameterized with respect to the optimal queuing length of a clairvoyant adversary. This gives a better picture of LQF's performance under heavy traffic than the usual (unparameterized) competitive ratio. We also discuss randomization, and we conclude with some intriguing open problems regarding a two-dimensional generalization of the problem.
This paper presents an algorithm for sampling and triangulating a smooth surface S in R3 where the triangulation is homeomorphic to S. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely computations of the intersection points of a line with the surface, computations of the critical points of some height functions defined on the surface and its restriction to a plane, and computations of some silhouette points. The algorithm ensures bounded aspect ratio, size optimality, and smoothness of the output triangulation. Unlike previous algorithms, this algorithm does not need to compute the local feature size for generating the sample points which was a major bottleneck. Experiments show the usefulness of the algorithm in remeshing and meshing CAD surfaces that are piecewise smooth.
In this paper we discuss the problem of constructing minimum-cost, prefix-free codes for equiprobable words under the assumption that all codewords are restricted to belonging to an arbitrary language L and extend the classes of languages to which L can belong.
Note: This extended abstract is essentially the version which appears in The proceedings of WADS'05, but with extra diagrams added.
We define simple-regular expressions and languages. Simple-regular languages provide a necessary condition for a language to be outfix-free. We design algorithms that compute simple-regular languages from finite-state automata. Furthermore, we investigate the complexity blowup from a given finite-state automaton to its simple-regular language automaton and show that there is an exponential blowup. In addition, we present a finite-state automata construction for simple-regular expressions based on state expansion.