Browsing by Author "Shieh, Min-Zheng"

Now showing 1 - 15 of 15

Arranging numbers on circles to reach maximum total variations
(2007-06-28)
Liao, Ying-Jie
;
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
The dartboard problem is to arrange n numbers on a circle to obtain maximum risk, which is the sum of the q-th power of the absolute differences of adjacent numbers, for q >= 1. Curtis showed that the dartboard problem admits a greedy algorithm. We generalize the dartboard problem by considering more circles and the goal is to arrange kn number on k circles to obtain the maximum risk. In this paper, we characterize an optimal arrangement for k = 2 and show that the generalized dartboard problem also admits a greedy algorithm.
BigraphTalk: Verified Design of IoT Applications
(2020-04-01)
Archibald, Blair
;
Shieh, Min-Zheng
;
Hu, Yu-Hsuan
;
Sevegnani, Michele
;
Lin, Yi-Bing
Graphical Internet of Things (IoT) device management platforms, such as IoTtalk, make it easy to describe interactions between IoT devices. Applications are defined by dragging-and-dropping devices and specifying how they are connected, e.g., a door sensor controlling a light. While this allows simple and rapid development, it remains possible to specify unwanted device configurations, such as using the same device to drive a motor up and down simultaneously, risking damaging the motor. We propose BigraphTalk, a verification framework for IoTtalk that utilizes formal techniques, based on bigraphs, to statically guarantee that unwanted configurations do not arise. In particular, we check for invalid connections between devices, as well as type errors, e.g., passing a float to a Boolean switch. To the best of our knowledge, BigraphTalk is the first platform to support the graphical specification of correct-by-design IoT applications. BigraphTalk provides fully automated verification and feedback without end-users ever needing to specify a bigraph. This means that any application, specifiable in IoTtalk, is guaranteed, so long as verification succeeds, not to violate the given configuration constraints when deployed; with no extra cost to the user.
CampusTalk: IoT Devices and Their Interesting Features on Campus Applications
(2018-01-01)
Lin, Yi-Bing
;
Chen, Li-Kuan
;
Shieh, Min-Zheng
;
Lin, Yun-Wei
;
Yen, Tai-Hsiang
Internet of Things (IoT) allows interactive learning of students by inspiring their innovation everywhere on the campus. This paper proposes CampusTalk that provides convenient access to cyber and physical devices through the web technology. In this way, the campus applications can be accessed anywhere in the world through any computing device with a display and a browser without installing any mobile app. CampusTalk unifies the concepts of automatic creation of "mirror device features'' (simulated counterpart) and talkPal device features, which are nicely demonstrated through several applications on campus. The core application of CampusTalk is SmartPhoneTalk that allows other applications to be accessed by students through their smartphones without installing any mobile apps. We describe three CampusTalk applications, including MusicTalk, PingPongTalk, and SkeletonTalk, to demonstrate cyber and physical interaction with SmartPhoneTalk. After the IoT devices of these applications have been developed and are accommodated in CampusTalk, the students can use the CampusTalk GUI to connect them with various combinations for innovative applications without extra programming effort.
Computing the Ball Size of Frequency Permutations under Chebyshev Distance
(2011)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
Let S-n(lambda) be the set of all permutations over the multiset [GRAPHICS] where n = m lambda. A frequency permutation array (FPA) of minimum distance d is a subset of S-n(lambda) in which every two elements have distance at least d. FPAs have many applications related to error correcting codes. In coding theory, the Gilbert- Varshamov bound and the spherepacking bound are derived from the size of balls of certain radii. We propose two efficient algorithms that compute the ball size of frequency permutations under Chebyshev distance. Both methods extend previous known results. The first one runs in O((()(2d lambda)2.376)(d lambda) log n) time and O((()(2d lambda)2)(d lambda)) space. The second one runs in O ((()(2d lambda)()(d lambda) (d lambda+lambda))(lambda)n/lambda) time and O((2d lambda)(d lambda)) space. For small constants lambda and d, both are efficient in time and use constant storage space.
Computing the ball size of frequency permutations under Chebyshev distance
(2012-07-01)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
Let S-n(lambda) be the set of all permutations over the multiset { [GRAPHICS] , .... , [GRAPHICS] } where n = m lambda. A frequency permutation array (FPA) of minimum distance d is a subset of S-n(lambda) which every two elements have distance at least d. FPAs have many applications related to error correcting codes. In coding theory, the Gilbert-Varshamov bound and the sphere-packing bound are derived from the size of balls of certain radii. We propose two efficient algorithms that compute the ball size of frequency permutations under Chebyshev distance. Here it is equivalent to computing the permanent of a special type of matrix, which generalizes the Toepliz matrix in some sense. Both methods extend previous known results. The first one runs in O (((2d lambda)(d lambda))(2.376) log n) time and O(((2d lambda)(d lambda))(2)) space. The second one runs in O (((2d lambda)(d lambda)) ((d lambda+lambda)(lambda))n/lambda) time and O (((2d lambda)(d lambda))) space. For small constants lambda and d, both are efficient in time and use constant storage space. (C) 2012 Elsevier Inc. All rights reserved.
Decoding Frequency Permutation Arrays Under Chebyshev Distance
(2010-11-01)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
A frequency permutation array (FPA) of length n = m lambda and distance d is a set of permutations on a multiset over m symbols, where each symbol appears exactly lambda times and the distance between any two elements in the array is at least d. FPA generalizes the notion of permutation array. In this paper, under the Chebyshev distance, we first prove lower and upper bounds on the size of FPA. Then we give several constructions of FPAs, and some of them come with efficient encoding and decoding capabilities. Moreover, we show one of our designs is locally decodable, i.e., we can decode a message bit by reading at most lambda + 1 symbols, which has an interesting application to private information retrieval.
Decoding Frequency Permutation Arrays Under Chebyshev Distance
(2010-11-01)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
A frequency permutation array (FPA) of length n = m lambda and distance d is a set of permutations on a multiset over m symbols, where each symbol appears exactly lambda times and the distance between any two elements in the array is at least d. FPA generalizes the notion of permutation array. In this paper, under the Chebyshev distance, we first prove lower and upper bounds on the size of FPA. Then we give several constructions of FPAs, and some of them come with efficient encoding and decoding capabilities. Moreover, we show one of our designs is locally decodable, i.e., we can decode a message bit by reading at most lambda + 1 symbols, which has an interesting application to private information retrieval.
Decoding Frequency Permutation Arrays under Infinite norm
(2009)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
A frequency permutation array (FPA) of length n = rn lambda), and distance d is a set of permutations on a multiset over m symbols, where each symbol appears exactly lambda times and the distance between any two elements in the array is at least d. FPA generalizes the notion of permutation array. In this paper, under the distance metric l(infinity)-norm, we first prove lower and upper bounds on the size of FPA. Then we give a construction of FPA with efficient encoding and decoding capabilities. Moreover, we show our design is locally decodable, i.e., we can decode a message bit by reading at most lambda + 1 symbols, which has an interesting application for private information retrieval.
Decoding permutation arrays with ternary vectors
(2011-10-01)
Lee, Chia-Jung
;
Lin, Te-Tsung
;
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
Wu, Hsin-Lung
We give an explicit decoding scheme for the permutation arrays under Hamming distance metric, where the encoding is constructed via a distance-preserving mapping from ternary vectors to permutations (3-DPM).
Improved Bound on Approximating Jug Measuring Problem
(2011-05-01)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
In this note, we investigate the hardness of approximating the optimal jug measuring problem, which studies how to use jugs with certain capacities to measure a given quantity in minimum steps. Based on a recent related development, we prove that it is NP-hard to approximate this problem within n(c/loglog n) for some constant c > 0. This improves previous known result significantly.
Inapproximability Results for the Weight Problems of Subgroup Permutation Codes
(2012-11-01)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
生物科技學系
;
資訊工程學系
;
Department of Biological Science and Technology
A subgroup permutation code is a set of permutations on n symbols with the property that its elements are closed under the operation of composition. In this paper, we give inapproximability results for the minimum and maximum weight problems of subgroup permutation codes under several well-known metrics. Based on previous works, we prove that under Hamming, Lee, Cayley, Kendall's tau, Ulam's, and l(p) distance metrics, 1) there is no polynomial-time 2(log1-epsilon n)-approximation algorithm for the minimum weight problem for any constant epsilon > 0 unless NP subset of DTIME(2(polylog(n)))(quasi-polynomial time), and 2) there is no polynomial-time r-approximation algorithm for the minimum weight problem for any constant r > 1 unless P = NP. Under L-infinity-metric, we prove that it is NP-hard to approximate the minimum weight problem within factor 2 - epsilon for any constant epsilon > 0. We also prove that for any constant epsilon > 0, it is NP-hard to approximate the maximum weight within p root 3/2 - epsilon under l(p) distance metric, and within 3/2 - epsilon under Hamming, Lee, Cayley, Kendall's tau, and Ulam's distance metrics. Index Terms-Approximation algorithms,
Jug measuring: Algorithms and complexity
(2008-05-10)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
We study the hardness of the optimal jug measuring problem. By proving tight lower and upper bounds on the minimum number of measuring steps required, we reduce an inapproximable NP-hard problem (i.e., the shortest GCD multiplier problem [G. Havas, J.-P. Seifert, The Complexity of the Extended GCD Problem, in: LNCS, vol. 1672, Springer, 1999]) to it. It follows that the optimal jug measuring problem is NP-hard and so is the problem of approximating the minimum number of measuring steps within a constant factor. Along the way, we give a polynomial-time approximation algorithm with an exponential error based on the well-known LLL basis reduction algorithm. (C) 2008 Elsevier B.V. All rights reserved.
More on the Magnus-Derek game
(2011-02-04)
Chen, Li-Jui
;
Lin, Jinn-Jy
;
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
We consider the so called Magnus-Derek game, which is a two-person game played on a round table with n positions. The two players are called Magnus and Derek. Initially there is a token placed at position O. In each round Magnus chooses a positive integer m <= n/2 as the distance of the targeted position from his current position for the token to move, and Derek decides a direction, clockwise or counterclockwise, to move the token. The goal of Magnus is to maximize the total number of positions visited, while Derek's is to minimize this number. If both players play optimally, we prove that Magnus, the maximizer, can achieve his goal in O(n) rounds, which improves a previous result with O(n log n) rounds. Then we consider a modified version of the Magnus-Derek game, where one of the players reveals his moves in advance and the other player plays optimally. In this case we prove that it is NP-hard for Derek to achieve his goal if Magnus reveals his moves in advance. On the other hand, Magnus has an advantage to occupy all positions. We also consider the circumstance that both players play randomly, and we show that the expected time to visit all positions is O(n log n). (c) 2010 Elsevier B.V. All rights reserved.
On the inapproximability of maximum intersection problems
(2012-10-15)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
Yang, Ming-Chuan
;
資訊工程學系
;
Department of Computer Science
Given a sets, we want to choose exactly k sets such that the cardinality of their intersection is maximized. This is the so-called MAX-k-INTERSECT problem. We prove that MAX-k-INTERSECT cannot be approximated within an absolute error of 1/2n(1-2 epsilon) + O(n(1-3 epsilon)) unless P = NP. This answers an open question about its hardness. We also give a correct proof of an inapproximable result by Clifford and Papa (2011) [3] by proving that MAX-INTERSECT problem is equivalent to the MAX-CLIQUE problem. (C) 2012 Elsevier B.V. All rights reserved.
On the minimum weight problem of permutation codes under Chebyshev distance
(2010)
Shieh, Min-Zheng
;
Tsai, Shi-Chun
;
資訊工程學系
;
Department of Computer Science
Permutation codes of length n and distance d is a set of permutations on n symbols, where the distance between any two elements in the set is at least d. Subgroup permutation codes are permutation codes with the property that the elements are closed under the operation of composition. In this paper, under the distance metric l(infinity)-norm, we prove that finding the minimum weight codeword for subgroup permutation code is NP-complete. Moreover, we show that it is NP-hard to approximate the minimum weight within the factor 7/6 - epsilon for any epsilon > 0.