Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem

被引：1

作者：

Ye, Deshi ^{[1
]}

Zhang, Guochuan ^{[1
]}

机构：

[1] Zhejiang Univ, Coll Comp Sci, Hangzhou 310027, Zhejiang, Peoples R China

来源：

COMPUTING AND COMBINATORICS | 2015年 / 9198卷

关键词：

Mechanism design; Knapsack auction; Approximation algorithms; ALGORITHMS; RECTANGLES;

D O I：

10.1007/978-3-319-21398-9_31

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper provides a technique for designing truthful mechanisms for a combinatorial optimization problem, which requires composition algorithms. We show that the composition algorithm A o B is monotone if the algorithm A and the algorithm B are both monotone. Then, we apply this technique to the two-dimensional orthogonal knapsack problem with provable approximation bounds, improving the previous results in [5].

引用

页码：390 / 401

页数：12

共 50 条

[31] Two-dimensional local Hamiltonian problem with area laws is QMA-complete
Huang, Yichen
JOURNAL OF COMPUTATIONAL PHYSICS, 2021, 443
[32] Precise design of two-dimensional diffractive optical elements for beam shaping
Qu, Weidong
Gu, Huarong
Tan, Qiaofeng
Jin, Guofan
APPLIED OPTICS, 2015, 54 (21) : 6521 - 6525
[33] An Object-Oriented Design for Two-Dimensional Vortex Particle Methods
Ramachandran, Prabhu
Ramakrishna, M.
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2009, 36 (04):
[34] The two-dimensional cutting stock problem within the roller blind production process
de Gelder, E. R.
Wagelmans, A. P. M.
STATISTICA NEERLANDICA, 2009, 63 (04) : 474 - 489
[35] An efficient evolutionary algorithm applied to the design of two-dimensional IIR filters
Das, Swagatam
Konar, Amit
Chakraborty, Uday K.
GECCO 2005: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOLS 1 AND 2, 2005, : 2157 - 2163
[36] Design of Regular One-Dimensional, Two-Dimensional, and Three-Dimensional Linkage-Based Tessellations
Yellowhorse, Alden D.
Brown, Nathan
Howell, Larry L.
JOURNAL OF MECHANISMS AND ROBOTICS-TRANSACTIONS OF THE ASME, 2020, 12 (02):
[37] 2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems
Silva, Elsa
Oliveira, Jose F.
Waescher, Gerhard
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 237 (03) : 846 - 856
[38] The two-dimensional cutting stock problem with usable leftovers: mathematical modelling and heuristic approaches
do Nascimento, Douglas Nogueira
Cherri, Adriana Cristina
Oliveira, Jose Fernando
OPERATIONAL RESEARCH, 2022, 22 (05) : 5363 - 5403
[39] The bi-objective two-dimensional loading vehicle routing problem with partial conflicts
Hamdi-Dhaoui, Khaoula
Labadie, Nacima
Yalaoui, Alice
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2014, 52 (19) : 5565 - 5582
[40] Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts
Khanafer, Ali
Clautiaux, Francois
Talbi, El-Ghazali
COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (01) : 54 - 63

← 1 2 3 4 5 →