岩間研究室 発表論文

2010年度

[ 論文誌 ]

id=2010-06

K. Iwama, K. Seto, and S. Tamaki,

``The Planar Hajos Calculus for Bounded Degree Graphs'',

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E93-A, no.6, pp.1000--1007, Jun. 2010.

 

>> Abstract

id=2010-14

David Manlove, Robert W. Irving, and Kazuo Iwama,

``Guest Editorial: Special Issue on Matching Under Preferences.'',

Algorithmica, vol.58, no.1, pp.1--4, Sep. 2010.

id=2010-15

Kazuo Iwama, and Guochuan Zhang,

``Online knapsack with resource augmentation.'',

Inf. Process. Lett., vol.110, no.22, pp.1016--1020, Oct. 2010.

id=2010-16

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

``On the Boolean Connectivity Problem for Horn Relations'',

Discrete Applied Mathematics, vol.158, no.18, pp.2024--2030, Nov. 2010.

 

>> Abstract

id=2010-17

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

``Approximation Algorithms for the Sex-Equal Stable Marriage Problem'',

ACM Transactions on Algorithms, vol.7, 1/2, Nov. 2010.

 

>> Abstract

id=2010-22

Hiroshi Fujiwara, Kazuo Iwama, and Yoshiyuki Sekiguchi,

``Average-case competitive analyses for one-way trading.'',

Journal of Combinatorial Optimization, vol.21, no.1, pp.83--107, Jan. 2011.

id=2010-20

Wolfgang W. Bein, Kazuo Iwama, Jun Kawahara, Lawrence L. Larmore, and James A. Oravec,

``A randomized algorithm for two servers in cross polytope spaces.'',

Theoretical Computer Science, vol.412, no.7, pp.563-572, Feb. 2011.

id=2010-28

Y. Yoshida, and H. Ito,

``Property testing on k-vertex connectivity of graphs'',

Algorithmica, vol.to appear., , (発表月不明) .

 

>> Abstract

[ 国際会議 ]

id=2010-01

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

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

Proc. of the 3rd Asian Association for Algorithms and Computation (AAAC 2010), pp., Apr. 2010.

id=2010-02

K. Iwama, K. Seto, and S. Tamaki,

``Enumerating Non-3-colorable Planar Graphs by the Haj坦s Calculus'',

Proc. of the 3rd Asian Association for Algorithms and Computation (AAAC 2010), pp.24, Apr. 2010.

id=2010-03

K. Iwama, T. Takai, and S. Tamaki,

``Improved Randomized Algorithms for 3-SAT'',

Proc. of the 3rd Asian Association for Algorithms and Computation (AAAC 2010), pp.41, Apr. 2010.

id=2010-04

H. Morizumi,

``The Size and Width of Boolean Circuits'',

Proc. of the 3rd Asian Association for Algorithms and Computation (AAAC 2010), pp.45, Apr. 2010.

id=2010-05

Kazuo Iwama, H. Nishimura, R. Raymond, and J. Teruyama,

``Quantum Counterfeit Coin Problems'',

Proc. of the 3rd Asian Association for Algorithms and Computation (AAAC 2010), pp., Apr. 2010.

id=2010-08

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

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

The 13th International Conference on Theory and Applications of Satisfiability Testing Proc. SAT 2010, LNCS 6175, pp.172--180, Jul. 2010.

 

>> Abstract

id=2010-10

K. Ueno,

``Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds'',

Proc. 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), LNCS 6281, pp.665--676, Aug. 2010.

 

>> Abstract

id=2010-11

S. Tamaki, and Y. Yoshida,

``A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness'',

Proc. 14th Intl. Workshop on Randomization and Computation (RANDOM 2010), pp.738--751, Sep. 2010.

 

>> Abstract

id=2010-12

Y. Yoshida, and H. Ito,

``Testing Outerplanarity of Bounded Degree Graphs'',

Proc. 14th Intl. Workshop on Randomization and Computation (RANDOM 2010), pp.642--655, Sep. 2010.

 

>> Abstract

id=2010-13

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

``A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties'',

Proc. 18th Annual European Symposium on Algorithms (ESA 2010), LNCS 6347, pp.135--146, Sep. 2010.

 

>> Abstract

id=2010-18

K. Iwama, K. Seto, T. Takai, and S. Tamaki,

``Improved Randomized Algorithms for 3-SAT'',

The 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS 6506, pp.73--84, Dec. 2010.

 

>> Abstract

id=2010-19

K. Iwama, H. Nishimura, R. Raymond, and J. Teruyama,

``Quantum Counterfeit Coin Problems'',

The 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS 6506, pp.85--96, Dec. 2010.

id=2010-20

Y. Yoshida,

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

Proc. 43rd ACM Symposium on Theory of Computing (STOC 2011), pp.665--674, Jan. 2011.

 

>> Abstract

id=2010-21

Y. Yoshida,

``Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs'',

Proc. 26th IEEE Conference on Computational Complexity (CCC 2011), pp.34--44, Jan. 2011.

 

>> Abstract

[ 国内発表 ]

id=2010-09

玉置卓,

``3SATに対する乱択アルゴリズムの改良'',

ERATO湊離散構造処理系＋NEO 合同研究会, 2010年 7月.

id=2010-23

H. Ito, J. Teruyama, Y. Yoshida,

``Bubble Sort with Infinitely Large Bins'',

冬のLAシンポジウム, pp.25.1--25.7, 2011年 2月.

 

>> Abstract

id=2010-25

伊藤大雄, 清島奨, 吉田悠一,

``ナップサック問題に対する定数時間近似アルゴリズム'',

電子情報通信学会 コンピューテーション研究会, 信学技報, vol.110, no.464, COMP2010-51, pp.29--36, 2011年 3月.

 

>> Abstract

id=2010-26

吉田悠一,

``次数制限モデルにおける全てのCSPに対する最適な定数時間近似アルゴリズムと近似困難性'',

電子情報通信学会 総合大会, vol., pp.(to appear), 2011年 3月.

id=2010-27

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

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

電子情報通信学会 総合大会, vol., pp.S-21--S-22, 2011年 3月.

[ その他 ]

id=2010-07

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

``A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties'',

IBM Research Report RT0913, Jun. 2010.

id=2010-24

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

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

arXiv:1102.3766v1 [cs.CC], Feb. 2011.

id=2010-29

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

``Constant-Time Algorithms for Sparsity Matroids'',

arXiv:1103.2581v1 [cs.CC], Mar. 2011.

Abstract

id=2010-06

The planar Haj\'os calculus (\phc) is the Haj\'os calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. The degree-$d$ planar Haj\'os calculus (\phcd{d}) is \phc \ with the restriction that all the graphs that appear in the construction (including a final graph) must have maximum degree at most $d$. We prove the followings: (1) If \phc \ is polynomially bounded, then for any $d \geq 4$, \phcd{d+2} \ can generate any non-3-colorable planar graphs of maximum degree at most $d$ in polynomial steps. (2) If \phc \ can generate any non-3-colorable planar graphs of maximum degree 4 in polynomial steps, then \phc \ is polynomially bounded.

id=2010-08

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=2010-10

Karchmer, Kushilevitz and Nisan formulated the formula size problem as an integer programming problem called the rectangle bound and introduced a technique called the LP bound, which gives a formula size lower bound by showing a feasible solution of the dual problem of its LP-relaxation. As extensions of the LP bound, we introduce novel general techniques proving formula size lower bounds, named a quasi-additive bound and the Sherali-Adams bound. While the Sherali-Adams bound is potentially strong enough to give a lower bound matching to the rectangle bound, we prove that the quasi-additive bound can surpass the rectangle bound.

id=2010-11

Long Code testing is a fundamental problem in the area of property testing and hardness of approximation. Long Code is a function of the form $f(x)=x_i$ for some index $i$. In the Long Code testing, the problem is, given oracle access to a collection of Boolean functions, to decide whether all the functions are the same Long Code, or cross-influences of any two functions are small. In this paper, we study the following problem: How small the soundness $s$ of the Long Code test with perfect completeness can be by using non-adaptive $q$ queries? We give a Long Code test with $s=(2q+3)/2^q$, where $q$ is of the form $2^k-1$ for any integer $k>2$. Our test is a ``noisy'' version of Samorodnitsky-Trevisan's Hyper Graph linearity test with suitably chosen noise distribution. To bound the soundness, we use Invariance-Principle style analysis in the spirit of O'Donnell and Wu (STOC 2009). Previously, H\r{a}stad and Khot (Theory of Computing, 2005) have shown $s=2^{4\sqrt{q}}/2^q$ for infinitely many $q$. Chen (RANDOM 2009) has improved this to $s=q^3/2^q$ for infinitely many $q$ with ``adaptive'' queries. As for the Long Code test with ``almost'' perfect completeness, Samorodnitsky and Trevisan (SICOMP, 2009) have shown $s=2q/2^q$ (or even $(q+1)/2^q$ for infinitely many $q$). Austrin and Mossel (Computational Complexity, 2009) have improved this to $s=(q+o(q))/2^q$ (or even $(q+4)/2^q$ assuming the famous Hadamard Conjecture) for any $q$.

id=2010-12

We present an efficient algorithm for testing outerplanarity of graphs in the bounded degree model. In this model, given a graph $G$ with $n$ vertices and degree bound $d$, we should distinguish with high probability the case that $G$ is outerplanar from the case that modifying at least an $\epsilon$-fraction of the edge set of $G$ is necessary to make $G$ outerplanar. Our algorithm runs in $\tilde{O}\left(\frac{1}{\epsilon^{13}d^6}+\frac{d}{\epsilon^2}\right)$ time, which is independent of the size of graphs. This is the first algorithm for a non-trivial minor-closed property whose time complexity is polynomial in $\frac{1}{\epsilon}$ and $d$. To achieve the time complexity, we exploit the tree-like structure inherent to an outerplanar graph using the microtree/macrotree decomposition of a tree. As a corollary, we also show an algorithm that tests whether a given graph is a cactus with time complexity $\tilde{O}\left(\frac{1}{\epsilon^{13}d^6}+\frac{d}{\epsilon^2}\right)$.

id=2010-13

The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within $33/29 \ (> 1.1379)$ unless P=NP, and the current best approximation algorithm achieves the ratio of $1.5$. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within $21/19 \ (> 1.1052)$ unless P=NP. However, even under this restriction, the best known approximation ratio is still $1.5$. In this paper, we improve it to $25/17 \ (< 1.4706)$.

id=2010-16

Gopalan {\em et~al.} studied in [Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), pp. 346--357, 2006] and [SIAM J. Comput., 38(6):2330--2355, 2009] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the connectivity problems in Schaefer's framework. A set $S$ of logical relations is $\schaefer$ if all relations in $S$ are either bijunctive, Horn, dual Horn, or affine. They first conjectured that the connectivity problem for $\schaefer$ is in $\P$. We disprove their conjecture by showing that there exists a set $S$ of Horn relations such that the connectivity problem for $S$ is $\coNP$-complete. We also investigate a tractable aspect of Horn and dual Horn relations with respect to characteristic sets.

id=2010-17

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 {\em 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.

id=2010-18

This pager gives a new randomized algorithm which solves 3-SAT in time $O(1.32113^n)$. The previous best bound is $O(1.32216^n)$ due to Rolf (J.~SAT,~2006). The new algorithm uses the same approach as Iwama and Tamaki (SODA~2004), but exploits the non-uniform initial assignment due to Hofmeister et al. (STACS 2002) against the Sch\"oning's local search (FOCS~1999).

id=2010-20

Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it. In this paper, we show that similar results hold for constant-time approximation algorithms in the bounded-degree model. Specifically, we present the followings: (i) For every CSP, we construct an oracle that serves an access, in constant time, to a nearly optimal solution to a basic LP relaxation of the CSP. (ii) Using the oracle, we give a constant-time rounding scheme that achieves an approximation ratio coincident with the integrality gap of the basic LP. (iii) Finally, we give a generic conversion from integrality gaps of basic LPs to hardness results. All of those results are \textit{unconditional}. Therefore, for every bounded-degree CSP, we give the best constant-time approximation algorithm among all. A CSP instance is called $\epsilon$-far from satisfiability if we must remove at least an $\epsilon$-fraction of constraints to make it satisfiable. A CSP is called testable if there is a constant-time algorithm that distinguishes satisfiable instances from $\epsilon$-far instances with probability at least $2/3$. Using the results above, we also derive, under a technical assumption, an equivalent condition under which a CSP is testable in the bounded-degree model.

id=2010-21

In this paper, we consider lower bounds on the query complexity for testing CSPs in the bounded-degree model. We mainly consider Boolean CSPs allowing literals. First, for any ``symmetric'' predicate $P:\{0,1\}^{k}\to \{0,1\}$ except \textsf{EQU} where $k\geq 3$, we show that every (randomized) algorithm that distinguishes satisfiable instances of \textsf{CSP}($P$) from instances $(|P^{-1}(0)|/2^k-\epsilon)$-far from satisfiability requires $\Omega(n^{1/2+\delta})$ queries where $n$ is the number of variables and $\delta>0$ is a constant that depends on $P$ and $\epsilon$. This breaks a natural lower bound $\Omega(n^{1/2})$, which is obtained by the birthday paradox. We also show that every one-sided error tester requires $\Omega(n)$ queries for such $P$. These results are hereditary in the sense that the same results hold for any predicate $Q$ such that $P^{-1}(1)\subseteq Q^{-1}(1)$. For \textsf{EQU}, we give a one-sided error tester whose query complexity is $\tilde{O}(n^{1/2})$. Also, for \textsf{$2$-XOR} (or, equivalently \textsf{E2LIN2}), we show an $\Omega(n^{1/2+\delta})$ lower bound for distinguishing instances between $\epsilon$-close to and $(1/2-\epsilon)$-far from satisfiability. Next, for the general \textsf{$k$-CSP} over the binary domain, we show that every algorithm that distinguishes satisfiable instances from instances $(1-2k/2^k-\epsilon)$-far from satisfiability requires $\Omega(n)$ queries. The matching NP-hardness is not known, even assuming the Unique Games Conjecture or the $d$-to-$1$ Conjecture. As a corollary, for \mislong on graphs with $n$ vertices and a degree bound $d$, we show that every approximation algorithm within a factor $d/\poly\log d$ and an additive error of $\epsilon n$ requires $\Omega(n)$ queries. Previously, only super-constant lower bounds were known.

id=2010-23

id=2010-25

id=2010-28

We present an algorithm for testing the $k$-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound $d$, a graph $G$ with $n$ vertices and a maximum degree at most $d$ is called $\epsilon$-far from $k$-vertex-connectivity when at least $\frac{\epsilon dn}{2}$ edges must be added to or removed from $G$ to obtain a $k$-vertex-connected graph with a maximum degree at most $d$. The algorithm always accepts every graph that is $k$-vertex-connected and rejects every graph that is $\epsilon$-far from $k$-vertex-connectivity with a probability of at least $2/3$. The algorithm runs in $O\left(d\left(\frac{c}{\epsilon d}\right)^{k}\log\frac{1}{\epsilon d}\right)$ time $(c>1 \mbox{ is a constant})$ for $(k-1)$-vertex-connected graphs, and in $O\left(d\left(\frac{ck}{\epsilon d}\right)^{k}\log\frac{k}{\epsilon d}\right)$ time $(c>1 \mbox{ is a constant})$ for general graphs. It is the first constant-time $k$-vertex-connectivity testing algorithm for general $k\geq 4$.