ログイン
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 研究者一覧
  2. 原口 和也
  1. 学術雑誌論文

Iterated Local Search with Trellis-Neighborhood for the Partial Latin Square Extension Problem

http://hdl.handle.net/10252/00005804
http://hdl.handle.net/10252/00005804
90aed977-1162-42d0-9ebd-124775163d23
名前 / ファイル ライセンス アクション
Journal Journal of Heuristics_22_5_ pp 727–757 (1.3 MB)
Item type 学術雑誌論文 / Journal Article(1)
公開日 2018-07-04
タイトル
タイトル Iterated Local Search with Trellis-Neighborhood for the Partial Latin Square Extension Problem
言語 en
言語
言語 eng
資源タイプ
資源タイプ識別子 http://purl.org/coar/resource_type/c_6501
資源タイプ journal article
著者 Haraguchi, Kazuya

× Haraguchi, Kazuya

WEKO 166

en Haraguchi, Kazuya

Search repository
著者別名
識別子Scheme WEKO
識別子 32472
姓名 原口, 和也
言語 ja
書誌情報 en : Journal of Heuristics

巻 22, 号 5, p. 727-757, 発行日 2016-10
出版者
出版者 Springer US
言語 en
ISSN / EISSN
収録物識別子タイプ PISSN
収録物識別子 1381-1231
DOI
関連タイプ isVersionOf
識別子タイプ DOI
関連識別子 https://doi.org/10.1007/s10732-016-9317-6
書誌ID(NCID)
収録物識別子タイプ NCID
収録物識別子 AA12120967
出版社版URI
言語 ja
権利情報 https://doi.org/10.1007/s10732-016-9317-6
テキストバージョン
出版タイプ AM
出版タイプResource http://purl.org/coar/version/c_ab4af688f83e57aa
日本十進分類法
言語 ja
主題Scheme NDC
主題 007
NIIサブジェクト
言語 ja
主題Scheme Other
主題 情報学
NIIサブジェクト
言語 ja
主題Scheme Other
主題 数学
抄録
内容記述タイプ Abstract
内容記述 A partial Latin square (PLS) is a partial assignment of n symbols to an n x n grid such that, in each row and in each column, each symbol appears at most once. The partial Latin square extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by (p, q)-swap, i.e.,the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient (p,∞)-neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for p ∈ {1, 2, 3}. The runnin time of the algorithm is O(nP+1). We then propose a novel swap operation, Trellisswap,which is a generalization of (p, q)-swap with p≤2. The proposed Trellis-neighborhood search algorithm runs in O(n3·5) time. The iterated local search (ILS) algorithm with Trellisneighborhood is more likely to deliver a high-quality solution than not only ILSs with (p, ∞)neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LOCALSOLVER.
言語 en
戻る
0
views
See details
Views

Versions

Ver.1 2023-05-15 16:07:00.409950
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR 2.0
  • OAI-PMH JPCOAR 1.0
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3