岩間研究室 発表論文

2011年度

[ 論文誌 ]

id=2011-04

J. Akiyama, H. Ito, M. Kobayashi, and G. Nakamura,

``Arrangements of n points whose incident-line-numbers are at most n/2'',

Graphs and Combinatorics, vol.27, no.3, pp.321--326, May 2011.

id=2011-11

K. Makino, S. Tamaki, and M. Yamamoto,

``An Exact Algorithm for the Boolean Connectivity Problem for k-CNF'',

Theoretical Computer Science, vol.412, no.35, pp.4613--4618, Aug. 2011.

 

>> Abstract

id=2011-26

H. Ito, Y. Teruyama, and Y. Yoshida,

``An Almost Optimal Algorithm for Winkler's Sorting Pairs in Bins'',

Progress in Informatics, no.9, pp.3--7, Mar. 2012.

[ 国際会議 ]

id=2011-01

H. Ito, S. Tanigawa, and Y. Yoshida,

``Testing Graph Rigidity in Constant Time'',

Proc. 4th Asian Association for Algorithms and Computation (AAAC 2011), pp.?, Apr. 2011.

id=2011-02

R. Cleve, K. Iwama, F. Le Gall, H. Nishimura, S. Tani, J. Teruyama, and S. Yamashita,

``Reconstructing Strings from Substrings with Quantum Queries'',

Proc. 4th Asian Association for Algorithms and Computation (AAAC 2011), pp.?, Apr. 2011.

id=2011-03

K. Ueno,

``Parity versus Majority: Formula Complexity Perspective'',

Proc. 4th Asian Association for Algorithms and Computation (AAAC 2011), pp.35, Apr. 2011.

id=2011-05

K. Iwama, S. Miyazaki, and H. Yanagisawa,

``Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects'',

Proc. of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), LNCS 6648, pp.440--451, May 2011.

 

>> Abstract

id=2011-06

T. Inoshita, R. W. Irving, K. Iwama, S. Miyazaki, and T. Nagase,

``Improving Man-Optimal Stable Matchings by Minimum Change of Preference Lists'',

Proc. of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2011), pp.309--313, May 2011.

 

>> Abstract

id=2011-07

H. Ito, S. Tanigawa, and Y. Yoshida,

``Testing algorithms for (k,l)-sparsity and (k,l)-edge-connected orientability'',

Proc. of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ2011), pp.447--456, May 2011.

id=2011-09

Y. Yoshida,

``Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP'',

Sublinear Algorithms 2011, May 2011.

id=2011-12

T. Umesato, T. Saitoh, R. Uehara, and H. Ito,

``Complexity of the stamp folding problem'',

Proc. of the 5th Annual International Conference on Combinatorial Optimization and Applications (COCOA 11), LNCS 6831, pp.311--321, Aug. 2011.

id=2011-13

J. Cardinal, H. Ito, M. Korman, and S. Langerman,

``Helly numbers of polyominoes'',

The 23rd Canadian Conference on Computational Geometry, pp.443--448, Aug. 2011.

id=2011-14

H. Ito, and S. Takart,

``PSPACE-completeness of the weighted poset game'',

Proc. of the 10th International Symposium on Operations Research and Its Applications (ISORA 2011), LNOR 14, pp.89--93, Aug. 2011.

id=2011-15

K. Makino, S. Tamaki, and M. Yamamoto,

``Derandomizing HSSW algorithm for 3-SAT'',

The 17th Annual International Computing and Combinatorics Conference Proc. of COCOON 2011, LNCS 6842, pp.1--12, Aug. 2011.

 

>> Abstract

id=2011-16

F. Le Gall, and Y. Yoshida,

``Property Testing for Cyclic Groups and Beyond'',

Proc. of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011), pp.432--443, Aug. 2011.

 

>> Abstract

id=2011-17

K. Hamada, K. Iwama, and S. Miyazaki,

``The Hospitals/Residents Problem with Quota Lower Bounds'',

Proc. of the 19th Annual European Symposium on Algorithms (ESA 2011), LNCS 6942, pp.181--191, Sep. 2011.

 

>> Abstract

id=2011-18

Yusuke Kobayashi, and Yuichi Yoshida,

``Algorithms for Finding a Maximum Non-k-linked Graph'',

Proc. of the 19th European conference on Algorithms (ESA 2011), LNCS 6942, pp.131--142, Sep. 2011.

 

>> Abstract

id=2011-19

W. Bein, N. Hatta, N. Hernandez-Cons, H. Ito, S. Kasahara, and J. Kawahara,

``An Online Algorithm Optimally Self-Tuning to Congestion for Power Management Problems'',

Proc. 9th Workshop on Approximation and Online Algorithms (WAOA 2011), pp.35--48, Sep. 2011.

 

>> Abstract

id=2011-20

Eric Blais, Amit Weinstein, and Yuichi Yoshida,

``Testing Juntas of Symmetric Functions'',

China Theory Week 2011, Oct. 2011.

id=2011-22

D. Avis, K. Iwama, and D. Paku,

``Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs'',

The 22nd International Symposium on Algorithms and Computation (ISAAC 2011), LNCS 7074, pp.415--424, Dec. 2011.

 

>> Abstract

id=2011-23

G. Kun, R. O'Donnell, S. Tamaki, Y. Yoshida, and Y. Zhou,

``Linear programming, width-1 CSPs, and robust satisfaction'',

Proc. of the 3rd Innovations in Theoretical Computer Science (ITCS2012), pp.484-495, Jan. 2012.

 

>> Abstract

[ 国内発表 ]

id=2011-08

吉田悠一,

``Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP'',

画期における最適化, 2011年 5月.

id=2011-10

G. Kun, R. O'Donnell, S. Tamaki, Y. Yoshida, Y. Zhou,

``Linear Programming Robustly Decides Width-1 CSPs'',

2011年夏のLAシンポジウム, 2011年 7月.

id=2011-21

上野賢哉,

``論理式の複雑さを明らかにする理論'',

学術情報メディアセンタセミナー, 2011年 10月.

id=2011-24

上野賢哉,

``多数決３分木への論理式分解'',

冬のLAシンポジウム, pp.2.1--2.8, 2012年 1月.

id=2011-25

K. Seto, S. Tamaki,

``A Satisfiability Algorithm for Formulas over the Full Binary Basis'',

冬のLAシンポジウム, pp.??--??, 2012年 1月.

Abstract

id=2011-05

Manlove and O'Malley~\cite{mo08} proposed the Student-Project Allocation Problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algorithm. In this paper, we give an improved upper bound of 1.5 and a lower bound of $21/19 \ (>1.1052)$.

id=2011-06

In the stable marriage problem, any instance admits the so-called {\em man-optimal stable matching}, in which every man is assigned the best possible partner. However, there are instances for which all men receive low-ranked partners even in the man-optimal stable matching. In this paper we consider the problem of improving the man-optimal stable matching by changing only one man's preference list. We show that the optimization variant and the decision variant of this problem can be solved in time $O(n^{3})$ and $O(n^{2})$, respectively, where $n$ is the number of men (women) in an input.

id=2011-11

We present an exact algorithm for a PSPACE-complete problem, denoted by $\CONN k\SAT$, which asks if the solution space for a given $k$-CNF formula is connected on the $n$-dimensional hypercube. The problem is known to be PSPACE-complete for $k\geq 3$, and polynomial solvable for $k\leq 2$ \cite{GKMP06}. We show that $\CONN k\SAT$ for $k\geq 3$ is solvable in time $O((2-\epsilon_k)^n)$ for some constant $\epsilon_k>0$, where $\epsilon_k$ depends only on $k$, but not on $n$. This result is considered to be interesting due to the following fact shown by \cite{Cal09}: QBF-3-SAT, which is a typical PSPACE-complete problem, is not solvable in time $O((2-\epsilon)^n)$ for any constant $\epsilon>0$, provided that the SAT problem (with no restriction to the clause length) is not solvable in time $O((2-\epsilon)^n)$ for any constant $\epsilon>0$.

id=2011-15

We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by Hofmeister, Sch\"oning, Schuler, and Watanabe in [STACS'02]. Thereby, we obtain an $\exprun(1.3303^n)$-time deterministic algorithm for 3-SAT, which is currently fastest.

id=2011-16

This paper studies the problem of testing if an input $(\Gamma,\circ)$, where $\Gamma$ is a finite set of unknown size and $\circ$ is a binary operation over $\Gamma$ given as an oracle, is close to a specified class of groups. Friedl et al.~[\emph{Efficient testing of groups}, STOC'05] have constructed an efficient tester using $\poly(\log|\Gamma|)$ queries for the class of abelian groups. We focus in this paper on subclasses of abelian groups, and show that these problems are much harder: $\Omega(|\Gamma|^{1/6})$ queries are necessary to test if the input is close to a cyclic group, and $\Omega(|\Gamma|^{c})$ queries for some constant $c$ are necessary to test more generally if the input is close to an abelian group generated by $k$ elements, for any fixed integer $k\ge 1$. We also show that knowledge of the size of the ground set $\Gamma$ helps only for $k=1$, in which case we construct an efficient tester using $\poly(\log|\Gamma|)$ queries; for any other value $k\ge 2$ the query complexity remains $\Omega(|\Gamma|^{c})$. All our upper and lower bounds hold for both the edit distance and the Hamming distance. These are, to the best of our knowledge, the first nontrivial lower bounds for such group-theoretic problems in the property testing model and, in particular, they imply the first exponential separations between the classical and quantum query complexities of testing closeness to classes of groups.

id=2011-17

The Hospitals/Residents problem is a many-to-one extension of the stable marriage problem. In its instance, each hospital specifies a quota, i.e., an upper bound on the number of positions it provides. It is well-known that in any instance, there exists at least one stable matching, and finding one can be done in polynomial time. In this paper, we consider an extension in which each hospital specifies not only an upper bound but also a {\em lower} bound on its number of positions. In this setting, there can be instances that admit no stable matching, but the problem of asking if there is a stable matching is solvable in polynomial time. In case there is no stable matching, we consider the problem of finding a matching that is ``as stable as possible'', namely, a matching with a minimum number of blocking pairs. We show that this problem is hard to approximate within the ratio of $(|H|+|R|)^{1-\epsilon}$ for any positive constant $\epsilon$ where $H$ and $R$ are the sets of hospitals and residents, respectively. We tackle this hardness from two different angles. First, we give an exponential-time exact algorithm for a special case where all the upper bound quotas are one. This algorithm runs in time $O(t^{2}(|H|(|R|+t))^{t+1})$ for instances whose optimal cost is $t$. Second, we consider another measure for optimization criteria, i.e., the number of residents who are involved in blocking pairs. We show that this problem is still NP-hard but has a polynomial-time $\sqrt{|R|}$-approximation algorithm.

id=2011-18

A graph with at least $2k$ vertices is said to be {$k$-linked} if for any ordered $k$-tuples $(s_1, \dots , s_k)$ and $(t_1, \dots , t_k)$ of $2k$ distinct vertices, there exist pairwise vertex-disjoint paths $P_1, \dots , P_k$ such that $P_i$ connects $s_i$ and $t_i$ for $i=1, \dots , k$. For a given graph $G$, we consider the problem of finding a maximum induced subgraph of $G$ that is not $k$-linked. This problem is a common generalization of computing the vertex-connectivity and testing the $k$-linkedness of $G$, and it is closely related to the concept of $H$-linkedness. In this paper, we give a first polynomial-time algorithm for the case of $k=2$, whereas a similar problem that finds a maximum induced subgraph without $2$-vertex-disjoint paths connecting fixed terminal pairs is NP-hard. For the case of general $k$, we give an $(8k-2)$-additive approximation algorithm. We also investigate the computational complexities of the edge-disjoint case and the directed case.

id=2011-19

We consider the classical power management problem: There is a device which has two states ON and OFF and one has to develop a control algorithm for changing between these states as to minimize (energy) cost when given a sequence of service requests. Although an optimal 2-competitive algorithm exists, that algorithm does not have good performance in many practical situations, especially in case the device is not used frequently. To take the frequency of device usage into account, we construct an algorithm based on the concept of ``slackness degree.'' Then by relaxing the worst case competitive ratio of our online algorithm to $2 + \varepsilon$, where $\varepsilon$ is an arbitrary small constant, we make the algorithm flexible to slackness. The algorithm thus automatically tunes itself to slackness degree and gives better performance than the optimal 2-competitive algorithm for real world inputs. In addition to worst case competitive ratio analysis, a queueing model analysis is given and computer simulations are reported, confirming that the performance of the algorithm is high.

id=2011-22

J. Hopcroft and D. Sheldon originally introduced the PageRank game to investigate the self-interested behavior of web authors who want to boost their PageRank by using game theoretical approaches. The PageRank game is a multiplayer game where players are the nodes in a directed web graph and they place their outlinks to maximize their PageRank value. They give best response strategies for each player and characterize properties of $\alpha$-insensitive Nash equilibria. In this paper we consider PageRank games for undirected web graphs, where players are free to delete any of their bidirectional links if they wish. We study the problem of determining whether the given graph represents a Nash equilibrium or not. We give an $O(n^{2})$ time algorithm for a tree, and a parametric $O(2^{k}n^{4})$ time algorithm for general graphs, where $k$ is the maximum vertex degree in any biconnected component of the graph.

id=2011-23

We say that an algorithm robustly decides a constraint satisfaction problem $\Pi$ if it distinguishes at-least-$(1 − \epsilon)$-satisfiable instances from less-than-$(1 − r(\epsilon))$-satisfiable instances for some function $r(\epsilon)$ with $r(\epsilon) \to 0$ as $\epsilon \to 0$. In this paper we show that the canonical linear programming relaxation robustly decides $\Pi$ if and only if $\Pi$ has “width 1” (in the sense of Feder and Vardi).