We investigate the power-down mechanism which decides when a machine transitions between states such that the total energy consumption, characterized by execution cost, idle cost and switching cost, is minimized. In contrast to most of the previous studies on the offline model, we focus on the online model in which a sequence of jobs with their release time, execution time and deadline, arrive in an online fashion. More precisely, we exploit a different switching on and off strategy and present an upper bound of 3, and further show a lower bound of 2.1, in a dual-machine model, introduced by Chen et al. in 2014 [STACS 2014: 226-238], both of which beat the currently best result.

The online car-sharing problem finds many real-world applications. The problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and k total cars. Each request which specifies its pick-up time and pick-up location (among 0 and 1, and the other is the drop-off location) is released in each stage a fixed amount of time before its specified start (i.e. pick-up) time. The time between the booking (i.e. released) time and the start time is enough to move empty cars between 0 and 1 for relocation if they are not used in that stage. The model, called k S2L-F, assumes that requests in each stage arrive sequentially regardless of the same booking time and the decision (accept or reject) must be made immediately. The goal is to accept as many requests as possible. In spite of only two locations, the analysis does not seem easy and the (tight) competitive ratio (CR) is only known to be 2 for k = 2 and 1.5 for a restricted value of k , i.e., a multiple of three. In this paper, we remove all the holes of unknown CR's; namely we prove that the CR is 2 k k + ⌊ k / 3 ⌋ for all k ≥ 2 . Furthermore, if the algorithm can delay its decision until all requests have come in each stage, the CR is improved to roughly 4/3. We can take this advantage even further; precisely we can achieve a CR of 2 + R 3 if the number of requests in each stage is at most Rk , 1 ≤ R ≤ 2 , where we do not have to know the value of R in advance. Finally we demonstrate that randomization also helps to get (slightly) better CR's, and prove some lower bounds to show the tightness.

The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear only in women's preference lists and (ii) each tie appears at the end of each woman's preference list. The current best lower bounds on the approximation ratio for this variant are 1.1052 unless P=NP and 1.25 under the unique games conjecture, while the current best upper bound is 1.4616. In this paper, we improve the upper bound to 1.25, which matches the lower bound under the unique games conjecture. Note that this is the first special case of the MAX SMTI where the tight approximation bound is obtained. The improved ratio is achieved via a new analysis technique, which avoids the complicated case-by-case analysis used in earlier studies. As a by-product of our analysis, we show that the integrality gap of natural IP and LP formulations for this variant is 1.25. We also show that the unrestricted MAX SMTI cannot be approximated with less than 1.5 unless the approximation ratio of a certain special case of the minimum maximal matching problem can be improved.

This paper studies property testing for NP optimization problems with parameter k under the general graph model with an augmentation of random edge sampling capability. It is shown that a variety of such problems, including k-Vertex Cover, k-Feedback Vertex Set, k-Multicut, k-path-freeness and k-Dominating Set, are constant-time testable if k is constant. It should be noted that the first four problems are fixed parameter tractable (FPT) and it turns out that algorithmic techniques for their FPT algorithms (branch-and-bound search, color coding, etc.) are also useful for our testers. k-Dominating Set is $W[2]$-hard, but we can still test the property in constant time since the definition of ε-farness makes the problem trivial for non-sparse graphs that are the source of hardness for the original optimization problem. We also consider k-Odd Cycle Transversal, which is another well-known FPT problem, but we only give a sublinear-time tester when k is a constant.

Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman and Santhanam introduced the tree evaluation problem (TEP). For fixed h, k>0, FT_h(k) is given as a complete, rooted binary tree of height h, in which each internal node is associated with a function from [k]^2 to [k], and each leaf node with a number in [k]. The value of an internal node v is defined naturally, i.e., if it has a function f and the values of its two child nodes are a and b, then the value of v is f(a,b). Our task is to compute the value of the root node by sequentially executing this function evaluation in a bottom-up fashion. The problem is obviously in P and if we could prove that any branching program solving FT_h(k) needs at least k^(r(h)) states for any unbounded function r, then this problem is not in L, thus achieving our goal. The above authors introduced a restriction called thrifty against the structure of BP’s (i,e., against the algorithm for solving the problem) and proved that any thrifty BP needs Omega(k^h) states. This paper proves a similar lower bound for read-once branching programs, which allows us to get rid of the restriction on the order of nodes read by the BP that is the nature of the thrifty restriction.

In the three-dimensional (3D) strip packing problem, we are given a set of 3D rectangular items and a 3D box $B$. The goal is to pack all the items in $B$ such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of $B$ and cannot be rotated. Building upon Caprara's work for the two-dimensional (2D) bin packing problem, we obtain an algorithm that, given any $\epsilon>0$, achieves an approximation of $T_{\infty}+\epsilon\approx1.69103+\epsilon$, where $T_{\infty}$ is the well-known number that occurs naturally in the context of bin packing. Our key idea is to establish a connection between bin packing solutions for an arbitrary instance $I$ and the strip packing solutions for the corresponding instance obtained from $I$ by applying the harmonic transformation to certain dimensions. Based on this connection, we also give a simple alternate proof of the $T_{\infty}+\epsilon$ approximation for 2D bin packing due to Caprara. In particular, we show how his result follows from a simple modification of the asymptotic approximation scheme for 2D strip packing due to Kenyon and Rémila.

The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this algorithm is man-optimal, that is, the matching is favorable for men but unfavorable for women, (or, if we exchange the roles of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem, posed by Gusfield and Irving, seeks a stable matching “fair” for both genders. Specifically it seeks a stable matching with the property that the sum of the men's scores is as close as possible to that of the women's. This problem is known to be strongly NP-hard. In this paper, we give a polynomial time algorithm for finding a near optimal solution for the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing an additional criterion: among stable matchings that are near optimal in terms of the sex-equality, find a minimum egalitarian stable matching. We show that this problem is strongly NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two.

In this article, we consider isolated cliques and isolated dense subgraphs. For a given graph G , a vertex subset S of size k (and also its induced subgraph G ( S )) is said to be c -isolated if G ( S ) is connected to its outside via less than ck edges. The number c is sometimes called the isolation factor . The subgraph appears more isolated if the isolation factor is smaller. The main result in this work shows that for a fixed constant c , we can enumerate all c -isolated maximal cliques (including a maximum one, if any) in linear time. In more detail, we show that, for a given graph G of n vertices and m edges, and a positive real number c , all c -isolated maximal cliques can be enumerated in time O ( c 4 2 2c m ). From this, we can see that: (1) if c is a constant, all c -isolated maximal cliques can be enumerated in linear time, and (2) if c = O (log n ), all c -isolated maximal cliques can be enumerated in polynomial time. Moreover, we show that these bounds are tight. That is, if f ( n ) is an increasing function not bounded by any constant, then there is a graph of n vertices and m edges for which the number of f ( n )-isolated maximal cliques is superlinear in n + m . Furthermore, if f ( n ) = ω(log n ), there is a graph of n vertices and m edges for which the number of f ( n )-isolated maximal cliques is superpolynomial in n + m . We next introduce the idea of pseudo-cliques. A pseudo-clique having an average degree α and a minimum degree β, denoted by PC (α,β), is a set V ′ ⊆ V such that the subgraph induced by V ′ has an average degree of at least α and a minimum degree of at least β. This article investigates these, and obtains some cases that can be solved in polynomial time and some other cases that have a superpolynomial number of solutions. Especially, we show the following results, where k is the number of vertices of the isolated pseudo-cliques: (1) For any ϵ > 0 there is a graph of n vertices for which the number of 1-isolated PC ( k - (log k ) 1 + ϵ , k /(log k ) 1 + ϵ ) is superpolynomial, and (2) there is a polynomial-time algorithm which enumerates all c -isolated PC ( k - log k , k /log k ), for any constant c .

Power-aware and energy-efficient designs play important roles for modern hardware and software designs, especially for embedded systems. This paper targets a scheduling problem on a processor with the capability of dynamic voltage scaling (DVS), which could reduce the power consumption by slowing down the processor speed. The objective of the targeting problem is to minimize the average flow time of a set of jobs under a given energy constraint, where the flow time of a job is defined as the interval length between the arrival and the completion of the job. We consider two types of processors, which have a continuous spectrum of the available speeds or have only a finite number of discrete speeds. Two algorithms are given: (1) An algorithm is proposed to derive optimal solutions for processors with a continuous spectrum of the available speeds. (2) A greedy algorithm is designed for the derivation of optimal solutions for processors with a finite number of discrete speeds. The proposed algorithms are extended to cope with jobs with different weights for the minimization of the average weighted flow time. The proposed algorithms are also evaluated with comparisons to schedules which execute jobs at a common effective speed.

The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this article, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of 2/(1 + L −2 ) for instances in which only men have ties of length at most L . When both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13/7(<1.858). We also improve the lower bound on the approximation ratio to 21/19(>1.1052).

An (n,1,p)-quantum random access (QRA) coding, introduced by Ambainis, Nayak, Ta-shma and Vazirani in ACM Symp. on Theory of Computing 1999, is the following communication system: The sender which has n-bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p, through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al. shows the existence of a (2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding and whether or not a (4,1,p)-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question

This paper gives a simple but nontrivial set of local transformation rules for Control-NOT(CNOT)-based combinatorial circuits. It is shown that this rule set is complete, namely, for any two equivalent circuits, S1 and S2, there is a sequence of transformations, each of them in the rule set, which changes S1 to S2. Our motivation is to use this rule set for developing a design theory for quantum circuits whose Boolean logic parts should be implemented by CNOT based circuits. As a preliminary example, we give a design procedure based on our transformation rules which reduces the cost of CNOT-based circuits.

No abstract available.

No abstract available.

We present a deterministic, oblivious, permutation-routing algorithm on the n × n mesh of constant queue-size. It runs in (2.954+ε)n steps for any ε > 0. Previously, an O(n)-time algorithm was known but with no nontrivial upper bounds on the constant factor.

Article Undecidability on quantum finite automata Share on Authors: Masami Amano School of Informatics, Kyoto University, Kyata 606-8501, Japan School of Informatics, Kyoto University, Kyata 606-8501, JapanView Profile , Kazuo Iwama School of Informatics, Kyoto University, Kyata 606-8501, Japan School of Informatics, Kyoto University, Kyata 606-8501, JapanView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 368–375https://doi.org/10.1145/301250.301344Online:01 May 1999Publication History 23citation442DownloadsMetricsTotal Citations23Total Downloads442Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Unlike the case of logspace-uniform circuits, complexity hierarchies do exist for PRAMs and DLOGTIME-uniform circuits: (i) There exist a constant d and a language L such that L is recognizable in time dT(n) by some PRIORITY CRCW PRAM but is not recognizable in time T(n) by any PRIORITY CRCW PRAM if the number of processors is fixed. (ii) There exist constants c, d and a language L such that L is recognizable by some family of DLOGTIME-uniform circuits of size (Z(n))/sup c/ and depth dT(n) but is not recognizable by any family of DLOGTIME-uniform circuits of size Z(n) and depth T(n) if T(n) is not bounded by O(log n).

Abstract The attempt of using random test circuits for evaluating the performance of logic optimizers like SIS is apparently new. To generate \\reasonable " random circuits, we propose the random applications of several transformation rules to an initial circuit instead of the obvious method, random placement of connections. A preliminary experiment has been conducted on SIS's responses against such random circuits. SIS shows considerably di erent performances for di erent circuits generated from the same original circuit. 1.

One of the common results of resource bounded Turing machines is the $\log \log n$ lower bound for the space usage of deterministic and nondeterministic Turing machines that accept nonregular languages. In this paper this result is extended to alternating Turing machines: It is proved that if $f(n) = o(\log \log n)$, then $f(n)$-space-bounded (off-line) alternating Turing machines can accept only regular sets. The problem has been open for a decade.

The average-case performance of an algorithm for CNF SAT, recently introduced by the author, is discussed. It is shown that the algorithm takes polynomial average time for a class of CNF equations satisfying the condition that for, a constant c, $p^2 v \geqq \ln t - c$, where v is the number of variables, t is the number of clauses, and p is the probability that a given literal appears in a clause. It was known that backtracking plus the pure literal rule, a common way of solving CNF SAT, takes polynomial average time if $p \geqq \varepsilon $ (any small constant) or $p \leqq c(\ln {v / v})^{{3 / 2}} $, but no algorithms were known to take polynomial average time (for all t) in the range $c(\ln v/v)^{3/2} < p < \varepsilon $. For reasonable $t(t \leqq v^\alpha $ for some constant $\alpha > 0$ the new algorithm runs in polynomial average time for $p > (\alpha \ln {v / v})^{{1 / 2}} $, so the unfavorable region is reduced to $c(\ln {v / v})^{{3 / 2}} < p < (\alpha \ln {v / v})^{{1 / 2}} $.

A string x is said to be decomposed into strings yl,Y2,...,yn if x is in y1 @@@@ y2 @@@@ ... @@@@ yn where @@@@ is the shuffle operator. We consider the problem of decomposing x into yl,Y2,...,yn such that yl,Y2,...,yn belong to predetermined languages L1,L2,...,Ln, respectively. Conditions under which such a decomposition is unique are presented as well as uniquely decomposable L1,L2,...,Ln which are of practical significance from the viewpoint of time-multiplexed communication.

S-equations are of the form E1(x1,..., xk) ⊇ E2 (X1,...,xk) where E1 and E2 are shuffle expressions having two types of symbols; variables and constants. E1⊇E2 is said to be S-satisfiable if the language expressed by E1(α1,...,αk) includes the language expressed by E2(α1,...,αk) where α1,...,αk are some strings of constants. A wide range of problems in string manipulation, data bases, etc., can be described in terms of S-equations. Major results include the solvability and complexity of several classes of S-satisfiability problems.