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 条

[41] No truthful mechanism can be better than n approximate for two natural problems
Leucci, Stefano
Mamageishvili, Akaki
Penna, Paolo
GAMES AND ECONOMIC BEHAVIOR, 2018, 111 : 64 - 74
[42] Generalized assignment problem: Truthful mechanism design without money
Fadaei, Salman
Bichler, Martin
OPERATIONS RESEARCH LETTERS, 2017, 45 (01) : 72 - 76
[43] Families of orthogonal two-dimensional wavelets
Maass, P
SIAM JOURNAL ON MATHEMATICAL ANALYSIS, 1996, 27 (05) : 1454 - 1481
[44] Two-Dimensional Orthogonal Grid Generation
Liu, Y. L.
Bai, K.
Wang, Xi
Liu, Mingqin
AUTOMATION EQUIPMENT AND SYSTEMS, PTS 1-4, 2012, 468-471 : 2668 - +
[45] EIGENMODES OF TWO-DIMENSIONAL ORTHOGONAL GRATINGS
GUDZENKO, AI
SOTIN, VE
RADIOTEKHNIKA I ELEKTRONIKA, 1986, 31 (12): : 2357 - 2363
[46] A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem
Goncalves, Jose Fernando
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 183 (03) : 1212 - 1229
[47] An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem
Russo, Mauro
Sforza, Antonio
Sterle, Claudio
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2013, 145 (02) : 451 - 462
[48] A PROBLEM IN TWO-DIMENSIONAL INTEGRATION
HENSTOCK, R
JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1983, 35 (DEC): : 386 - 404
[49] ON THE TWO-DIMENSIONAL MOMENT PROBLEM
Zagorodnyuk, Sergey
ANNALS OF FUNCTIONAL ANALYSIS, 2010, 1 (01): : 80 - 104
[50] A problem in two-dimensional flow
Macey, HH
PROCEEDINGS OF THE PHYSICAL SOCIETY, 1942, 54 : 128 - 134

← 1 2 3 4 5 →