researchmap

出版者・発行元：Springer  

The theory of two-sided matching has been extensively developed and applied
to many real-life application domains. As the theory has been applied to
increasingly diverse types of environments, researchers and practitioners have
encountered various forms of distributional constraints. Arguably, the most
general class of distributional constraints would be hereditary constraints; if
a matching is feasible, then any matching that assigns weakly fewer students at
each college is also feasible. However, under general hereditary constraints,
it is shown that no strategyproof mechanism exists that simultaneously
satisfies fairness and weak nonwastefulness, which is an efficiency (students'
welfare) requirement weaker than nonwastefulness. We propose a new
strategyproof mechanism that works for hereditary constraints called the
Multi-Stage Generalized Deferred Acceptance mechanism (MS-GDA). It uses the
Generalized Deferred Acceptance mechanism (GDA) as a subroutine, which works
when distributional constraints belong to a well-behaved class called
hereditary M$^\natural$-convex set. We show that GDA satisfies several
desirable properties, most of which are also preserved in MS-GDA. We
experimentally show that MS-GDA strikes a good balance between fairness and
efficiency (students' welfare) compared to existing strategyproof mechanisms
when distributional constraints are close to an M$^\natural$-convex set.

DOI： 10.1007/978-3-031-77367-9_30

arXiv

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/prima/prima2024.html#KimuraLSYY24

掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-031-78020-2_5

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/tcc/tcc2024-3.html#HanaokaKKTY24

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IOS Press  

DOI： 10.3233/FAIA240888

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/ecai/ecai2024.html#YoshidaKTY24

掲載種別：研究論文（学術雑誌）  

researchmap

その他リンク： https://dblp.uni-trier.de/db/journals/iacr/iacr2024.html#HanaokaKKTY24

We consider the problem of fair allocation with subsidy when agents have
weighted entitlements. After highlighting several important differences from
the unweighted cases, we present several results concerning weighted
envy-freeability including general characterizations, algorithms for achieving
and testing weighted envy-freeability, lower and upper bounds for worst case
subsidy for non-wasteful and envy-freeable allocations, and algorithms for
achieving weighted envy-freeability along with other properties.

DOI： 10.48550/arXiv.2408.08711

arXiv

researchmap

For simple graphs $G$ and $H$, the Hom complex $\mathrm{Hom}(G,H)$ is a
polyhedral complex whose vertices are the graph homomorphisms $G\to H$. It is
known that $\mathrm{Hom}(G,H)$ is homotopy equivalent to a disjoint union of
points and circles when both $G$ and $H$ are cycles. We generalize this known
result by showing that $\mathrm{Hom}(G,H)$ is homotopy equivalent to a disjoint
union of points and circles whenever $G$ is connected and $H$ is a cycle.

arXiv

researchmap

その他リンク： http://arxiv.org/pdf/2408.04802v1

Interdicting a criminal with limited police resources is a challenging task
as the criminal changes location over time. The size of the large
transportation network further adds to the difficulty of this scenario. To
tackle this issue, we consider the concept of a layered graph. At each time
stamp, we create a copy of the entire transportation network to track the
possible movements of both players, the attacker and the defenders. We consider
a Stackelberg game in a dynamic crime scenario where the attacker changes
location over time while the defenders attempt to interdict the attacker on his
escape route. Given a set of defender strategies, the optimal attacker strategy
is determined by applying Dijkstra's algorithm on the layered networks. Here,
the attacker aims to minimize while the defenders aim to maximize the
probability of interdiction. We develop an approximation algorithm on the
layered networks to find near-optimal strategy for defenders. The efficacy of
the developed approach is compared with the adopted MILP approach. We compare
the results in terms of computational time and solution quality. The quality of
the results demonstrates the need for the developed approach, as it effectively
solves the complex problem within a short amount of time.

DOI： 10.48550/arXiv.2406.14514

arXiv

researchmap

An online decision-making problem is a learning problem in which a player
repeatedly makes decisions in order to minimize the long-term loss. These
problems that emerge in applications often have nonlinear combinatorial
objective functions, and developing algorithms for such problems has attracted
considerable attention. An existing general framework for dealing with such
objective functions is the online submodular minimization. However, practical
problems are often out of the scope of this framework, since the domain of a
submodular function is limited to a subset of the unit hypercube. To manage
this limitation of the existing framework, we in this paper introduce the
online $\mathrm{L}^{\natural}$-convex minimization, where an
$\mathrm{L}^{\natural}$-convex function generalizes a submodular function so
that the domain is a subset of the integer lattice. We propose computationally
efficient algorithms for the online $\mathrm{L}^{\natural}$-convex function
minimization in two major settings: the full information and the bandit
settings. We analyze the regrets of these algorithms and show in particular
that our algorithm for the full information setting obtains a tight regret
bound up to a constant factor. We also demonstrate several motivating examples
that illustrate the usefulness of the online $\mathrm{L}^{\natural}$-convex
minimization.

DOI： 10.48550/arXiv.2404.17158

arXiv

researchmap

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2402.01084

researchmap

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2401.06405

researchmap

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>本発表では，一次元線分上の施設配置ゲーム，すなわち，参加するエージェントが一次元線分上の自分の位置を申告した際に，それらの申告から施設の配置を定める問題を考える．本発表では特に，Ordered Weighted Average メカニズムに着目し，その操作の非自明性について議論する．Ordered Weighted Average メカニズムとは，エージェントの申告の値を昇順に整列し，その順番に従って重みをかけ，その総和を返すようなメカニズムである．本発表では，それぞれの順序にかける重みを変えることにより，操作の非自明性がどのように変化するかを解析する．</p>

DOI： 10.11517/pjsai.jsai2024.0_2f6gs502

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とする．特に，線形補間によるL拡張可能性に着目し，そのような拡張が可能である整凸関数の特徴付けについて議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin235

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>情報伝播を伴うメカニズムはエージェントにインセンティブを与えできるだけ多くの同僚をメカニズムに参加させることと目的としている．情報伝播を伴う施設配置ゲームは耐戦略性，パレート効率性，匿名性を満たすメカニズムが存在しない不可能性定理が知られており，匿名性を満足しない耐戦略性，パレート効率性を満たすメカニズムが2つ知られている． 我々の目的は耐戦略性，パレート効率性を満たすメカニズムが他に存在するか検証することである． 本論文では匿名性に焦点を当てる．まず分割を導入して部分匿名性を定義し，耐戦略性，パレート効率性を満たすメカニズムが存在する分割の条件を明らかにした．</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin250

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>両方向のマッチング理論は広範囲に発展しており，学生の嫉妬を減少させ，総合的な福祉を向上させるようなマッチングを求めることが望まれている．しかし，効率性と公平性の間にはトレードオフが存在することが明らかになっている．そのため，本研究では，現実の世界で適用可能の一定の公平性を維持することで，効率性を向上させることを考える．我々の貢献はreverse Envy-Freeness up to k peers (r-EF-k; 最大k人の人物からのみ嫉妬を受け得る)と呼ばれるより弱い公平性の要件を提案することである．kを変化させることで，r-EF-kは異なる公平性のレベルを要求することができる．本研究では，一般的な制約下において，r-EF-kおよび効率性を満たすメカニズムについて議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_2f6gs501

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>行動経済学において，人は自分に近い人との比較で幸福度が決定するという仮説が提唱されている．この仮説に従い，本研究では，ソーシャルネットワーク上で直接つながっている相手に対してのみ嫉妬が発生する状況での両方向マッチングを考え，公平性と効率性の関係について検証する．特に，前述のような嫉妬を隣人への嫉妬として，また，隣人への嫉妬が存在しないという性質を局所公平性として定義し，これを従来の公平性の緩和として採用する．そして，マッチング市場における片側の選好を制限することで，隣人への嫉妬がなく（つまり，局所的に公平であり），かつパレート効率的であるマッチングの存在性およびそのようなマッチングを出力するメカニズムについて議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin2112

CiNii Research

出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

Consider a graph G where each vertex has a threshold. A vertex v in G is activated if the number of active vertices adjacent to v is at least as many as its threshold. A vertex subset A0 of G is a target set if eventually all vertices in G are activated by initially activating vertices of A0. The Target Set Selection problem (TSS) involves finding the smallest target set of G with vertex thresholds. This problem has already been extensively studied and is known to be NP-hard even for very restricted conditions. In this paper, we analyze TSS and its weighted variant, called the Weighted Target Set Selection problem (WTSS) from the perspective of parameterized complexity. Let k be the solution size and ℓ be the maximum threshold. We first show that TSS is W[1]-hard for split graphs when parameterized by k+ℓ, and W[2]-hard for cographs when parameterized by k. We also prove that WTSS is W[2]-hard for trivially perfect graphs when parameterized by k. On the other hand, we show that WTSS can be solved in O(nlogn) time for complete graphs. Additionally, we design FPT algorithms for WTSS when parameterized by nd+ℓ, tw+ℓ, ce, and vc, where nd is the neighborhood diversity, tw is the treewidth, ce is the cluster editing number, and vc is the vertex cover number of the input graph.

DOI： 10.1007/978-981-97-2340-9_27

Web of Science

Scopus

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>本論文では，時間の経過に伴い選好が変化する状況を捉えることのできる，2 期間を通じた両方向マッチングを考察する．このようなモデルでは，各期間で異なるエージェントとマッチングすることが可能である．従来の研究では，いずれの期間においても，エージェント一人，あるいはエージェントのペアが結託することで得をするようなことがないマッチングを動的安定なマッチングとして定義している． 本論文では，2 期間マッチングにおける新たな公平性および非浪費性，個人合理性を定義し，動的安定性との関係性について考察する．また，定義した公平性と非浪費性を同時に満たすマッチングの存在性について議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_1i3gs501

CiNii Research

掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2410.12884

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2411.05574

researchmap

掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1007/978-3-031-70362-1_19

Web of Science

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/pkdd/pkdd2024-5.html#YokoyamaIMKY24

出版者・発行元：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas  

The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. As a mechanism can handle a more general class of constraints, we can assign students more flexibly to colleges to increase students' welfare. However, it turns out that there exists a trade-off between students' welfare (efficiency) and fairness (which means no student has justified envy). Furthermore, this trade-off becomes sharper as the class of constraints becomes more general. The first contribution of this paper is to clarify the boundary on whether a strategyproof and fair mechanism can satisfy certain efficiency properties for each class of constraints. Our second contribution is to establish a weaker fairness requirement called envy-freeness up to k peers (EF-k), which is inspired by a similar concept used in the fair division of indivisible items. EF-k guarantees that each student has justified envy towards at most k students. By varying k, EF-k can represent different levels of fairness. We investigate theoretical properties associated with EF-k. Furthermore, we develop two contrasting strategyproof mechanisms that work for general hereditary constraints, i.e., one mechanism can guarantee a strong efficiency requirement, while the other can guarantee EF-k for any fixed k. We evaluate the performance of these mechanisms through computer simulation.

Scopus

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

DOI： 10.4230/LIPIcs.ISAAC.2023.47

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/isaac/isaac2023.html#KimuraM23

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2309.10968

researchmap

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2306.03368

researchmap

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とし，その準備となる証明を行った．具体的には，まず，半整数格子点上で整凸関数と同様の性質を持つ関数，半整凸関数を新たに定義する．そして，整凸関数が半整凸関数に緩和できる条件や，半整凸関数がL凸性を満たす条件を調べる．さらに，これらを利用することで，整凸関数がL拡張可能である条件を明らかにするための方向性を示す．</p>

DOI： 10.11517/pjsai.jsai2023.0_2j4gs102

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>一次元区間上の施設配置メカニズムの近似アルゴリズムによる解析において，エージェントの効用の最小値が大きいほどよいとされる平等性にもとづく目的関数や，エージェントの効用の総和が大きいほどよいとされる効率性にもとづいた目的関数が用いられた．目的関数に対する近似比は1に近いほどよいとされる．中点メカニズムは平等性に基づく目的関数で1の指標をもち，効率性に基づく目的関数でも比較的よい値をもつ．また，ナッシュメカニズムは平等性に基づく目的関数，効率性に基づく目的関数の双方で比較的1に近い値をもつ．しかし，中点メカニズムとナッシュメカニズムは戦略的操作が可能な場合が存在する． そこで，本研究では中点メカニズムとナッシュメカニズムに対してエージェントの申告値を考えることで，2種のメカニズムの戦略的操作の考察を行う． 結果として，中央値メカニズムはエージェントの申告値の区間が小さい場合にあるエージェントが効用を1にする戦略的操作が可能な場合が存在する．一方でナッシュメカニズムでは非常に多くのエージェントが特定の値を申告する場合に1人のエージェントの戦略的操作の影響が非常に小さくなることを示した．</p>

DOI： 10.11517/pjsai.jsai2023.0_2f5gs502

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>ヘドニックゲームは，エージェントのグループを適切なサブグループに分割する数理モデルで，従来協力ゲームの一分野として研究がなされてきた．一方，許可構造つきの協力ゲームは，エージェントのゲームへの参加が，別のエージェントによる許可制であるようなモデルである．本研究では，ヘドニックゲームに許可構造を導入し，情報拡散，すなわち，できる限り多くの許可を出すことのインセンティブが成立するヘドニックゲームの解について議論する．具体的には，まずナッシュ安定解と情報拡散が非両立であることを示す．この不可能性を受け，情報拡散のインセンティブを有するアルゴリズムを提案し，達成可能な社会的余剰の近似率を示す．</p>

DOI： 10.11517/pjsai.jsai2023.0_2f4gs503

CiNii Research

CiNii Research

記述言語：その他   出版者・発行元：Leibniz International Proceedings in Informatics, LIPIcs  

In the k-Recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. This problem is known to be solvable in polynomial time if k ≤ 3, and is PSPACE-complete if k ≥ 4. In this paper, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph -→R, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of recolorability constraints -→R, showing that the problem is solvable in linear time when -→R is a directed cycle or is in a class of multitrees.

DOI： 10.4230/LIPIcs.ISAAC.2022.4

Scopus

researchmap

記述言語：その他  

DOI： 10.1007/978-3-031-18530-4_23

記述言語：その他  

Quantaloidal approach to constraint satisfaction

記述言語：その他  

DOI： 10.1007/978-3-031-18530-4_23

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>マルチエージェント経路探索 (Multi-agent Pathfinding, MAPF) 問題は，それぞれ相異なるスタートとゴールが定められたエージェントの集合を入力とし，エージェント同士の衝突が発生しない経路の割当を解とする問題である．NP困難であることが知られている，各エージェントがゴールに到達するまでに要する時間の総和の最小化について，Meta-Agent Conflict Based Search (MA-CBS) と呼ばれる有力な厳密アルゴリズムが存在する．MA-CBS の動作は，マージポリシーと呼ばれる条件に応じて変化するが，従来用いられてきた静的なマージポリシーのもとでは，一部のMAPFインスタンスにおいて膨大な実行時間を要することが知られている．そこで本論文では，アルゴリズムの性質を動的に変化させる新たなマージポリシーを提案する．また，提案したマージポリシーを実装したアルゴリズムが，従来と比較して多様なインスタンスで効率的に動作することを計算機実験で示す．</p>

DOI： 10.11517/pjsai.jsai2022.0_1n1gs503

CiNii Research

CiNii Research

CiNii Research

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s13160-021-00464-0

記述言語：その他   掲載種別：研究論文（学術雑誌）  

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00453-021-00797-9

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2020.12.025

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1587/transfun.2019eap1101

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

Trichotomy for the Reconfiguration Problem of Integer Linear Systems.
In this paper, we consider the reconfiguration problem of integer linear<br />
systems. In this problem, we are given an integer linear system &#36;I&#36; and two<br />
feasible solutions &#36;oldsymbol{s}&#36; and &#36;oldsymbol{t}&#36; of &#36;I&#36;, and then asked<br />
to transform &#36;oldsymbol{s}&#36; to &#36;oldsymbol{t}&#36; by changing a value of only<br />
one variable at a time, while maintaining a feasible solution of &#36;I&#36;<br />
throughout. &#36;Z(I)&#36; for &#36;I&#36; is the complexity index introduced by Kimura and<br />
Makino (Discrete Applied Mathematics 200:67--78, 2016), which is defined by the<br />
sign pattern of the input matrix. We analyze the complexity of the<br />
reconfiguration problem of integer linear systems based on the complexity index<br />
&#36;Z(I)&#36; of given &#36;I&#36;. We then show that the problem is (i) solvable in constant<br />
time if &#36;Z(I)&#36; is less than one, (ii) weakly coNP-complete and<br />
pseudo-polynomially solvable if &#36;Z(I)&#36; is exactly one, and (iii)<br />
PSPACE-complete if &#36;Z(I)&#36; is greater than one. Since the complexity indices of<br />
Horn and two-variable-par-inequality integer linear systems are at most one,<br />
our results imply that the reconfiguration of these systems are in coNP and<br />
pseudo-polynomially solvable. Moreover, this is the first result that reveals<br />
coNP-completeness for a reconfiguration problem, to the best of our knowledge.

DOI： 10.1007/978-3-030-39881-1_29

記述言語：その他  

NP-Completeness of Fill-a-Pix and Sigma(P)(2)-Completeness of Its Fewest Clues Problem

DOI： 10.1587/transfun.E102.A.1490

記述言語：その他   掲載種別：研究論文（学術雑誌）  

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.7155/jgaa.00511

記述言語：その他  

A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition.

DOI： 10.1007/978-3-030-10564-8_17

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

Linear Satisfiability Preserving Assignments (Extended Abstract).

DOI： 10.24963/ijcai.2018/797

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.suscom.2018.02.007

記述言語：その他  

The Fewest Clues Problem of Picross 3D.

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

The Bounded Degree Deletion problem (BDD) is that of computing a minimum vertex set in a graph G=(V,E) with degree bound b: V=Z+, such that, when it is removed from G, the degree of any remaining vertex v is no larger than b(v). It is a classic problem in graph theory and various results have been obtained including an approximation ratio of 2+In bmax [30], where bmax is the maximum degree bound. This paper considers BDD on directed graphs containing unbounded vertices, which we call Partially Bounded Degree Deletion (PBDD). Despite such a natural generalization of standard BDD, it appears that PBDD has never been studied and no algorithmic results are known, approximation or parameterized. It will be shown that (1) in case all the possible degrees are bounded, in-degrees by and out-degrees by, BDD on directed graphs can be approximated within, and (2) although it becomes NP-hard to approximate PBDD better than bmax (even on undirected graphs) once unbounded vertices are allowed, it can be within when only in-degrees (and none of out-degrees) are partially bounded by b.

DOI： 10.1007/978-3-319-75172-6_4

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In this paper, we consider autark and linear autark assignments of Horn CNFs. We first study maximal autark assignments of Horn CNFs and devise a linear time algorithm of computing these assignments. This complements the previous work by Marek which reveals the properties of minimal autark assignments of Horn CNFs. We then consider linear autark assignments of Horn CNFs and give a combinatorial characterization of the existence of such an assignment. By making use of this characterization, we devise a linear time algorithm of finding linear autark assignments of Horn CNFs.

DOI： 10.1007/s13160-017-0284-6

記述言語：その他   掲載種別：研究論文（学術雑誌）  

In this paper, we study several classes of satisfiability preserving assignments to the constraint satisfaction problem (CSP). In particular, we consider fixable, autark and satisfying assignments. Since it is in general NP-hard to find a nontrivial (i.e., nonempty) satisfiability preserving assignment, we introduce linear satisfiability preserving assignments, which are defined by polyhedral cones in an associated vector space. The vector space is obtained by the identification, introduced by Kullmann, of assignments with real vectors. We consider arbitrary polyhedral cones, where only restricted classes of cones for autark assignments are considered in the literature. We reveal that cones in certain classes are maximal as a convex subset of the set of the associated vectors, which can be regarded as extensions of Kullmann's results for autark assignments of CNFs. As algorithmic results, we present a pseudo-polynomial time algorithm that computes a linear fixable assignment for a given integer linear system, which implies the well known pseudo-polynomial solvability for integer linear systems such as two-variable-per-inequality (TVPI), Horn and q-Horn systems.

DOI： 10.1613/jair.5658

リポジトリ公開URL： https://hdl.handle.net/2324/7172672

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

This paper studies optimal matroid partitioning problems for various objective functions. Inthe problem, we are given a finite set E and k weighted matroids (E, Ii,wi), i = 1, . . . , k, andour task is to find a minimum partition (I1, . . . , Ik) of E such that Ii 2 Ii for all i. For eachobjective function, we give a polynomial-Time algorithm or prove NP-hardness. In particular, forthe case when the given weighted matroids are identical and the objective function is the sum ofthe maximum weight in each set (i.e.,Pk i=1 maxe2Ii wi(e)), we show that the problem is strongly NP-hard but admits a PTAS.

DOI： 10.4230/LIPIcs.ISAAC.2017.51

記述言語：その他  

Optimal Matroid Partitioning Problems

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In this paper, we consider solving the integer linear systems, i.e., given a matrix A is an element of R-mxn a vector b is an element of R-m, and a positive integer d, to compute an integer vector x is an element of D-n such that Ax >= b or to determine the infeasibility of the system, where m and n denote positive integers, R denotes the set of reals, and D = {0, 1, ...,d-1). The problem is one of the most fundamental NP-hard problems in computer science.
For the problem, we propose a complexity index eta which depends only on the sign pattern of A. For a real gamma, let ILS(gamma) denote the family of the problem instances I with eta(I) = gamma. We then show the following trichotomy:
ILS(gamma) is solvable in linear time, if gamma < 1,
ILS(gamma) is weakly NP-hard and pseudo-polynomially solvable, if gamma = 1,
ILS(gamma) is strongly NP-hard, if gamma > 1.
This, for example, includes the previous results that Horn systems and two-variable-perinequality (TVPI) systems can be solved in pseudo-polynomial time. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.07.004

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Scheduling sensors to prolong the lifetime of covering targets in the field is one of the central problems in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear programming problem with exponential size, and has a constant-factor approximation algorithm. In reality, however, batteries of sensors have recovery effects, which is a phenomenon that the deliverable energy in batteries can be replenished by itself if it is left idling for sufficient duration. Thanks to that effects, we can obtain much longer lifetime of sensors if each sensor is forced to take a sleep at some interval. In this paper, we introduce two models that extend the MLCP, incorporating battery recovery effects. The first model represents battery recovery effects in a deterministic way, while the second one uses a probabilistic model to imitate the effects. We then propose efficient algorithms that work for both models by extending approximation algorithms for the original MLCP. Numerical experiments show that the lifetime of our schedule is 10-40% longer than one without battery recovery effects.

DOI： 10.1109/GLOCOM.2014.7036794

記述言語：その他  

Satisfiability Preserving Assignments and Their Local and Linear Forms

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

In this paper, we consider solving the integer linear systems, i.e., given a matrix A is an element of R-mxn, a vector b is an element of R-m, and a positive integer d, to compute an integer vector x is an element of D-n such that Ax >= b, where m and n denote positive integers, R denotes the set of reals, and D = {0, 1,..., d - 1}. The problem is one of the most fundamental NP-hard problems in computer science.
For the problem, we propose a complexity index eta which is based only on the sign pattern of A. For a real gamma, let ILS=(gamma) denote the family of the problem instances I with eta(I) = gamma. We then show the following trichotomy:
ILS=(gamma) is linearly solvable, if gamma < 1,
ILS=(gamma) is weakly NP-hard and pseudo-polynomially solvable, if gamma = 1, and
ILS=(gamma) is strongly NP-hard, if gamma > 1.
This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time.

DOI： 10.4230/LIPIcs.STACS.2012.613

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

Trichotomy for the reconfiguration problem of integer linear systems

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

Quantaloidal approach to constraint satisfaction

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

Neighborhood persistency of the linear optimization relaxation of integer linear optimization

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

Algorithms for coloring reconfiguration under recolorability digraphs

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：日本国  

記述言語：日本語  

国名：日本国  

Surface inspection using multipole modulated LED ring with correlation image sensor

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：日本語  

国名：日本国  

整数線形システムの実行可能性問題に対する計算複雑さの指標

記述言語：日本語  

国名：日本国  

記述言語：その他  

国名：その他  

Trichotomy for Integer Linear Systems Based on Their Sign Patterns

記述言語：その他  

国名：その他  

記述言語：日本語  

国名：日本国  

整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標

記述言語：日本語  

国名：日本国  

DS-1-6 A Complexity Index of Integer Linear Systems Based on Their Sign Patterns

記述言語：その他  

国名：その他  

A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：英語  

国名：その他  

A Complexity Index of Integer Linear Systems Based on Their Sign Patterns

記述言語：日本語  

国名：日本国  

制約充足問題に対する線形固定可能割当ての解析

記述言語：日本語  

国名：日本国  

制約充足問題に対する線形固定可能割当ての解析

記述言語：日本語  

国名：日本国  

DS-1-3 An Analysis of Linear Fixable Assignments for Constraint Satifcation Problem

記述言語：日本語  

国名：日本国  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

Maximum Lifetime Coverage Problems with Battery Recovery Effects

記述言語：その他  

国名：その他  

A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

記述言語：その他  

国名：その他  

記述言語：日本語  

国名：日本国  

整数線形不等式系の実行可能性問題における多項式時間可解部分クラス

記述言語：その他  

国名：その他  

Min-sum-max matroid partitioning problem

記述言語：その他  

国名：その他  

Optimal Matroid Partitioning Problems

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

記述言語：その他  

国名：その他  

Approximating Partially Bounded Degree Deletion on Directed Graphs

記述言語：その他  

国名：日本国  

researchmap

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

会議種別：口頭発表（一般）  

researchmap

researchmap