检索结果-内蒙古大学图书馆

30th International Symposium on algorithms and Computation, ISAAC 2019

作者： Hamada, Koki Miyazaki, Shuichi Yanagisawa, Hiroki NTT Corporation 3-9-11 Midori-cho Musashino-shi Tokyo180-8585 Japan Graduate School of Informatics Kyoto University Yoshida-Honmachi Sakyo-ku Kyoto606-8501 Japan Academic Center for Computing and Media Studies Kyoto University Yoshida-Honmachi Sakyo-ku Kyoto606-8501 Japan IBM Research - Tokyo 19-21 Hakozaki-cho Nihombashi Chuoh-ku Tokyo103-8510 Japan

ISBN: (纸本)9783959771306

In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the well-known stable mechanisms is the man-oriented Gale-Shapley algorithm (MGS). MGS has a good property that it is strategy-proof to the men's side, i.e., no man can obtain a better outcome by falsifying a preference list. We call such a mechanism a man-strategy-proof mechanism. Unfortunately, MGS is not a woman-strategy-proof mechanism. (Of course, if we flip the roles of men and women, we can see that the woman-oriented Gale-Shapley algorithm (WGS) is a woman-strategy-proof but not a man-strategy-proof mechanism.) Roth has shown that there is no stable mechanism that is simultaneously man-strategy-proof and woman-strategy-proof, which is known as Roth's impossibility theorem. In this paper, we extend these results to the stable marriage problem with ties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth's impossibility theorem takes over to SMTI. Therefore, we focus on the one-sided-strategy-proofness. In SMTI, one instance can have stable matchings of different sizes, and it is natural to consider the problem of finding a largest stable matching, known as MAX SMTI. Thus we incorporate the notion of approximation ratios used in the theory of approximation algorithms. We say that a stable-mechanism is a c-approximate-stable mechanism if it always returns a stable matching of size at least 1/c of a largest one. We also consider a restricted variant of MAX SMTI, which we call MAX SMTI-1TM, where only men's lists can contain ties (and women's lists must be strictly ordered). Our results are summarized as follows: (i) MAX SMTI admits both a man-strategy-proof 2-approximate-stable mechanism and a woman-strategy-proof 2-approximate-stable mechanism. (ii) MAX SMTI-1TM admits a woman-strategy-proof 2-approximate-stable mechanism. (iii) MAX SMTI-1TM admits a man-strategy-proof 1.5-approximate-stable mechanism. All these results are

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Replenishment Problems with Fixed Turnover Times 1

引用

13th Latin American Theoretical Informatics Symposium (LATIN)

作者： Bosman, Thomas van Ee, Martijn Jiao, Yang Marchetti-Spaccamela, Alberto Ravi, R. Stougie, Leen Vrije Univ Amsterdam Netherlands Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Sapienza Univ Rome Rome Italy CWI Amsterdam Netherlands INRIA Erable Paris France Netherlands Def Acad Den Helder Netherlands

ISBN: (数字)9783319774046

ISBN: (纸本)9783319774046;9783319774039

We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places;at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Almost optimal classical approximation algorithms for a quantum generalization of max-cut 22

Almost optimal classical approximation algorithms for a quan...

引用

22nd International Conference on approximation algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019

作者： Gharibian, Sevag Parekh, Ojas University of Paderborn Germany Virginia Commonwealth University RichmondVA United States Sandia National Laboratories AlbuquerqueNM United States

ISBN: (纸本)9783959771252

approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal;we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively. © Sevag Gharibian and Ojas Parekh.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for Adaptive Target Profit Maximization

Efficient Approximation Algorithms for Adaptive Target Profi...

引用

International Conference on Data Engineering

作者： Keke Huang Jing Tang Xiaokui Xiao Aixin Sun Andrew Lim School of Comp. Sci. and Engg. Nanyang Technological University Dept. of Ind. Syst. Engg. and Mgmt. National University of Singapore School of Computing National University of Singapore

ISBN: (数字)9781728129037

ISBN: (纸本)9781728129044

Given a social network G, the profit maximization (PM) problem asks for a set of seed nodes to maximize the profit, i.e., revenue of influence spread less the cost of seed selection. The target profit maximization (TPM) problem, which generalizes the PM problem, aims to select a subset of seed nodes from a target user set T to maximize the profit. Existing algorithms for PM mostly consider the nonadaptive setting, where all seed nodes are selected in one batch without any knowledge on how they may influence other users. In this paper, we study TPM in adaptive setting, where the seed users are selected through multiple batches, such that the selection of a batch exploits the knowledge of actual influence in the previous batches. To acquire an overall understanding, we study the adaptive TPM problem under both the oracle model and the noise model, and propose ADG and AddATP algorithms to address them with strong theoretical guarantees, respectively. In addition, to better handle the sampling errors under the noise model, we propose the idea of hybrid error based on which we design a novel algorithm HATP that boosts the efficiency of AddATP significantly. We conduct extensive experiments on real social networks to evaluate the performance, and the experimental results strongly confirm the superiorities and effectiveness of our solutions.

关键词： Adaptation models Social network services approximation algorithms Integrated circuit modeling Probabilistic logic Additives

来源：评论

学校读者我要写书评

暂无评论

Conditionally optimal approximation algorithms for the girth of a directed graph

arXiv

引用

arXiv 2020年

作者： Dalirrooyfard, Mina Williams, Virginia Vassilevska

The girth is one of the most basic graph parameters, and its computation has been studied for many decades. Under widely believed fine-grained assumptions, computing the girth exactly is known to require mn1−o(1) time, both in sparse and dense m-edge, n-node graphs, motivating the search for fast approximations. Fast good quality approximation algorithms for undirected graphs have been known for decades. For the girth in directed graphs, until recently the only constant factor approximation algorithms ran in O(nω) time, where ω 1−Ε) time for Ε > 0 and all sparsities m was only recently obtained by Chechik et al. [STOC 2020];it is also combinatorial. It is known that a better than 2-approximation algorithm for the girth in dense directed unweighted graphs needs n3−o(1) time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in O(mn1−Ε) time (by Chechik et al.) is 3. Is the true answer 2 or 3? The main result of this paper is a (conditionally) tight approximation algorithm for directed graphs. First, we show that under a popular hardness assumption, any algorithm, even one that exploits fast matrix multiplication, would need to take at least mn1−o(1) time for some sparsity m if it achieves a (2 − Ε)-approximation for any Ε > 0. Second we give a 2-approximation algorithm for the girth of unweighted graphs running in Õ(mn3/4) time, and a (2 + Ε)-approximation algorithm (for any Ε > 0) that works in weighted graphs and runs in Õ(m√n) time. Our algorithms are combinatorial. We also obtain a (4+Ε)-approximation of the girth running in Õ(mn√2−1) time, improving upon the previous best Õ(m√n) running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a (5+Ε)-approximate roundtrip spanner on Õ(n1.5/Ε2) edges in Õ(m√n/Ε2) time. This improves upon the previous approximation factor (8 + Ε) of Chechik et al. for the same running time. Copyright © 2020, The Author

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Distributionally Robust Stochastic Optimization with Black-Box Distributions

arXiv

引用

arXiv 2019年

作者： Linhares, André Swamy, Chaitanya Dept. of Combinatorics and Optimization University of Waterloo WaterlooONN2L 3G1 Canada

Two-stage stochastic optimization is a widely used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we make first-stage decisions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized. The goal is typically to minimize the total expected cost. A common criticism levied at this model is that the underlying probability distribution is itself often imprecise! To address this, an approach that is quite versatile and has gained popularity in the stochastic-optimization literature is the distributionally robust 2-stage model: given a collection D of probability distributions, our goal now is to minimize the maximum expected total cost with respect to a distribution in D. There has been almost no prior work however on developing approximation algorithms for distributionally robust problems, when the underlying scenario-set is discrete, as is the case with discrete-optimization problems. We provide a framework for designing approximation algorithms in such settings when the collection D is a ball around a central distribution and the central distribution is accessed only via a sampling black box. We first show that one can utilize the sample average approximation (SAA) method-solve the distributionally robust problem with an empirical estimate of the central distribution-to reduce the problem to the case where the central distribution has polynomial-size support. This follows because we argue that a distributionally robust problem can be reduced in a novel way to a standard 2-stage problem with bounded inflation factor, which enables one to use the SAA machinery developed for 2-stage problems. Complementing this, we show how to approximately solve a fractional relaxation of the SAA (i.e., polynomial-scenario central-distribution) problem. Unlike in

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Packing Directed Acyclic Graphs into Two-Size Blocks 18th

Approximation Algorithms for Packing Directed Acyclic Graphs...

引用

18th International Conference on Computational Science and Its Applications (ICCSA)

作者： Asahiro, Yuichi Miyano, Eiji Yagita, Tsuyoshi Kyushu Sangyo Univ Fukuoka Fukuoka Japan Kyushu Inst Technol Iizuka Fukuoka Japan

ISBN: (纸本)9783319951652;9783319951645

In this paper we consider the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short) and an integer B, the objective is to find a mapping of its nodes into blocks of size at most B that minimizes the maximum number of external arcs during traversals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. This paper focuses on the case B = 2. Even if B = 2 and the height of the DAG is three, it is known that the problem is NP-hard, and furthermore, there is no 3/2 - epsilon factor approximation algorithm for B = 2 and a small positive epsilon unless P = NP. On the other hand, the best approximation ratio previously shown is 3. In this paper we improve the approximation ratio into strictly smaller than 2. Also, we investigate the relationship between the height of input DAGs and the inapproximability, since the above inapproximability bound 3/2 - epsilon is shown only for DAGs of height 3.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Dense steiner problems: approximation algorithms and inapproximability

arXiv

引用

arXiv 2020年

作者： Karpinski, Marek Lewandowski, Mateusz Meesum, Syed Mohammad Mnich, Matthias Universität Bonn Institut für Informatik Bonn Germany University of Wrocaw Institute of Computer Science Wrocaw Poland Tu Hamburg Institute for Algorithms and Complexity Hamburg Germany

The Steiner Tree problem is a classical problem in com-binatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense version of Steiner Tree, where each terminal has at least δ|V(G) \ T| neighbours outside T, for a fixed δ > 0. They gave a PTAS for this problem. We study a generalization of pairwise δ-dense Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T1,... ,Tkare connected, and every terminal in Tihas at least δ|Tj| neighbours in Tj, and at least δ|S| nodes in S = V(G) \ (T1∪ · · · ∪ Tk), for each i,j in {1,... , k} with i ≠ j. Our first result is a polynomial-time approximation scheme for all δ > 1/2. Then, we show a (13/12 + ϵ)-approximation algorithm for δ = 1/2 and any ϵ > 0. We also consider the δ-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is APX-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for coordinating ad campaigns on social networks

arXiv

引用

arXiv 2019年

作者： Lakhotia, Kartik Kempe, David University of Southern California

We study a natural model of coordinated social ad campaigns over a social network, based on models of Datta et al. and Aslay et al. Multiple advertisers are willing to pay the host — up to a known budget — per user exposure, whether that exposure is sponsored or organic (i.e., shared by a friend). Campaigns are seeded with sponsored ads to some users, but no network user must be exposed to too many sponsored ads. As a result, while ad campaigns proceed independently over the network, they need to be carefully coordinated with respect to their seed sets. We study the objective of maximizing the network’s total ad revenue. Our main result is to show that under a broad class of social influence models, the problem can be reduced to maximizing a submodular function subject to two matroid constraints;it can therefore be approximated within a factor essentially 12 in polynomial time. When there is no bound on the individual seed set sizes of advertisers, the constraints correspond only to a single matroid, and the guarantee can be improved to 1 − 1/e;in that case, a factor 21 is achieved by a practical greedy algorithm. The 1 − 1/e approximation algorithm for the matroid-constrained problem is far from practical;however, we show that specifically under the Independent Cascade model, LP rounding and Reverse Reachability techniques can be combined to obtain a 1−1/e approximation algorithm which scales to several tens of thousands of nodes. Our theoretical results are complemented by experiments evaluating the extent to which the coordination of multiple ad campaigns inhibits the revenue obtained from each individual campaign, as a function of the similarity of the influence networks and the strength of ties in the network. Our experiments suggest that as networks for different advertisers become less similar, the harmful effect of competition decreases. With respect to tie strengths, we show that the most harm is done in an intermediate range. Copyright © 2019, The Authors.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for maximally balanced connected graph partition

arXiv

引用

arXiv 2019年

作者： Chen, Yong Chen, Zhi-Zhong Lin, Guohui Xu, Yao Zhang, An Department of Mathematics Hangzhou Dianzi University Hangzhou China Division of Information System Design Tokyo Denki University Saitama Japan Department of Computing Science University of Alberta EdmontonABT6G 2E8 Canada Department of Computer Science Kettering University FlintMI United States

Given a simple connected graph G = (V, E), we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The general vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm;the vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively;but no approximability result exists for k-BGP when k ≥ 4, except a trivial k-approximation. In this paper, we present another 3/2-approximation for our cardinality 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any constant k ≥ 3. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could be useful for related graph partition problems. Copyright © 2019, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：