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

QoE-Driven Adaptive Streaming for Point Clouds

IEEE TRANSACTIONS ON MULTIMEDIA 2023年 25卷 2543-2558页

作者： Wang, Lisha Li, Chenglin Dai, Wenrui Li, Shaohui Zou, Junni Xiong, Hongkai Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China

With increasing popularity of virtual reality and augmented reality, application of point clouds is in critical demand as it enables users to freely navigate in an immersive scene with six degrees of freedom. However, point clouds usually comprise large amounts of data, and are thus difficult to stream in bandwidth-constrained networks. It is therefore important, yet challenging, to efficiently stream the resource-intensive point clouds, such that the user's quality of experience (QoE) is guaranteed on a high-level but with a low bandwidth consumption. To this end, we propose a QoE-driven adaptive streaming approach for the tile-based point cloud transmission, to maximize the user's QoE while reducing the transmission redundancy. By exploiting the perspective projection, we specifically model the QoE of a 3D tile as a function of the bitrate of its representation, user's view frustum and spatial position, occlusion between tiles, and the resolution of rendering device. Based on this QoE model, we then formulate the QoE-optimized rate adaptation problem as a multiple-choice knapsack problem, which allocates bitrates for different tiles under a given transmission capacity. It is equivalently converted to a submodular function maximization problem subject to knapsack constraints, and solved by a practical greedy-based algorithm with a theoretical worst-case performance guarantee. The proposed algorithm is able to achieve a near-optimal performance, but with a very low computational complexity. Experimental results further demonstrate superiority of the proposed rate adaptation algorithm over existing schemes, in terms of both user's visual quality and transmission efficiency.

关键词： Point clouds rate adaptation perspective projection submodular function maximization MPEG G-PCC

来源：评论

学校读者我要写书评

暂无评论

Sequence independent lifting for a set of submodular maximization problems

引用

MATHEMATICAL PROGRAMMING 2022年第1-2期196卷 69-114页

作者： Shi, Xueyu Prokopyev, Oleg A. Zeng, Bo Univ Pittsburgh Dept Ind Engn Pittsburgh PA 15261 USA

We study the polyhedral structure of a mixed 0-1 set arising from the submodular maximization problem, given by P = ((w, x) is an element of R x (0, 1)(n) : w <= f (x), x is an element of X), where submodular function f (x) is represented by a concave function composed with an affine function, and X is the feasible region of binary variables x. For X = (0, 1)(n), two families of facet-defining inequalities are proposed for the convex hull of P through restriction and lifting using submodular inequalities. When X involves multiple disjoint cardinality constraints, we propose a new class of facet-defining inequalities for the convex hull of P through multidimensional sequence independent lifting. The derived polyhedral results not only strengthen and generalize some existing developments in the literature, but are also linked to the classical results for the mixed 0-1 knapsack and single-node flow sets. Our computational study on a set of randomly generated submodular maximization instances demonstrates the superiority of the proposed facet-defining inequalities within a branch-and-cut scheme.

关键词： submodular function maximization Sequence-independent lifting Polyhedra Multidimensional lifting Mixed 0-1 knapsack

来源：评论

学校读者我要写书评

暂无评论

submodular maximization Through the Lens o Linear Programming

引用

MATHEMATICS OF OPERATIONS RESEARCH 2019年第4期44卷 1221-1244页

作者： Bruggmann, Simon Zenklusen, Rico Swiss Fed Inst Technol Dept Math CH-8092 Zurich Switzerland

The simplex algorithm for linear programming is based on the fact that any local optimum with respect to the polyhedral neighborhood is also a global optimum. We show that a similar result carries over to submodular maximization. In particular, every local optimum of a constrained monotone submodular maximization problem yields a 1/2-approximation, and we also present an appropriate extension to the nonmonotone setting. Moreover, we describe a very general local search procedure that applies to a wide range of constraint families and unifies as well as extends previous methods. In our framework, we match known approximation guarantees while disentangling and simplifying previous approaches. Moreover, despite its generality, we are able to show that our local search procedure is slightly faster than previous specialized methods. Furthermore, we negatively answer the open question whether a linear optimization oracle may be enough to obtain strong approximation algorithms for submodular maximization. We do this by providing an example of a constraint family on a ground set of size n for which, if only given a linear optimization oracle, any algorithm for submodular maximization with a polynomial number of calls to the linear optimization oracle has an approximation ratio of only O(log n/(root n . log log n)).

关键词： submodular function maximization approximation algorithms local search hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint

引用

MATHEMATICAL PROGRAMMING 2022年第2期191卷 795-845页

作者： Bruggmann, Simon Zenklusen, Rico Swiss Fed Inst Technol Zurich Switzerland

Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the second step, where elements are dropped, is typically randomized. This leads to an additional source of randomization within the procedure, which can complicate the analysis. We suggest a different, polyhedral viewpoint to design contention resolution schemes, which avoids to deal explicitly with the randomization in the second step. This is achieved by focusing on the marginals of a dropping procedure. Apart from avoiding one source of randomization, our viewpoint allows for employing polyhedral techniques. Both can significantly simplify the construction and analysis of contention resolution schemes. We show how, through our framework, one can obtain an optimal monotone contention resolution scheme for bipartite matchings, which has a balancedness of 0.4762. So far, only very few results are known about optimality of monotone contention resolution schemes. Our contention resolution scheme for the bipartite case also improves the lower bound on the correlation gap for bipartite matchings. Furthermore, we derive a monotone contention resolution scheme for matchings that significantly improves over the previously best one. More precisely, we obtain a balancedness of 0.4326, improving on a prior 0.1997-balanced scheme. At the same time, our scheme implies that the currently best lower bound on the correlation gap for matchings is not tight. Our results lead to improved approximation factors for various constrained submodular function maximization problems over a combination of matching constraints with further constraints.

关键词： submodular function maximization Approximation algorithms Contention resolution schemes

来源：评论

学校读者我要写书评

暂无评论

Solving submodular text processing problems using influence graphs

引用

SOCIAL NETWORK ANALYSIS AND MINING 2019年第1期9卷 1-15页

作者： Vardasbi, Ali Faili, Heshaam Asadpour, Masoud Univ Tehran Coll Engn Sch Elect & Comp Engn Tehran Iran

submodular functions appear in a considerable number of important natural language processing problems such as text summarization and dataset selection. Current graph-based approaches to solving such problems do not pay special attention to the submodularity and simplistically do not learn the graph model. Instead, they roughly set the edge weights in the graph proportional to the similarity of their two endpoints. We argue that such a shallow modeling needs to be replaced by a deeper approach which learns the graph edge weights. As such, we propose a new method for learning the graph model corresponding the submodular function that is going to be maximized. In a number of real-world networks, our method leads to a 50% error reduction compared to the previously used baseline methods. Furthermore, we apply our proposed method followed by an influence maximization algorithm to two NLP tasks: text summarization and k-means initialization for topic selection. Using these case studies, we experimentally show the significance of our learning method over the previous shallow methods.

关键词： submodular function maximization Influence spread Extractive summarization K-means clustering Graph model

来源：评论

学校读者我要写书评

暂无评论

Deterministic Algorithms for submodular maximization Problems

引用

ACM TRANSACTIONS ON ALGORITHMS 2018年第3期14卷 1–20页

作者： Buchbinder, Niv Feldman, Moran Tel Aviv Univ Dept Stat & Operat Res IL-39040 Tel Aviv Israel Ecole Polytech Fed Lausanne Lausanne Switzerland Open Univ Israel Dept Math & Comp Sci IL-4353701 Raanana Israel

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work, we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing a submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

关键词： submodular function maximization derandomization unconstrained submodular maximization

来源：评论

学校读者我要写书评

暂无评论

Approximation Algorithms for submodular Data Summarization with a Knapsack Constraint

引用

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS 2021年第1期5卷 1–31页

作者： Han, Kai Cui, Shuang Zhu, Tianshuai Zhang, Enpei Wu, Benwei Yin, Zhizhuo Xu, Tong Tang, Shaojie Huang, He Univ Sci & Technol China SuZhou Res Inst Sch Comp Sci & Technol Hefei Anhui Peoples R China Univ Sci & Technol China Sch Comp Sci & Technol Hefei Anhui Peoples R China Univ Texas Dallas Naveen Jindal Sch Management Dallas TX USA Soochow Univ Sch Comp Sci & Technol Suzhou Jiangsu Peoples R China

Data summarization, i.e., selecting representative subsets of manageable size out of massive data, is often modeled as a submodular optimization problem. Although there exist extensive algorithms for submodular optimization, many of them incur large computational overheads and hence are not suitable for mining big data. In this work, we consider the fundamental problem of (non-monotone) submodular function maximization with a knapsack constraint, and propose simple yet effective and efficient algorithms for it. Specifically, we propose a deterministic algorithm with approximation ratio 6 and a randomized algorithm with approximation ratio 4, and show that both of them can be accelerated to achieve nearly linear running time at the cost of weakening the approximation ratio by an additive factor of is an element of. We then consider a more restrictive setting without full access to the whole dataset, and propose streaming algorithms with approximation ratios of 8 + is an element of and 6 + is an element of that make one pass and two passes over the data stream, respectively. As a by-product, we also propose a two-pass streaming algorithm with an approximation ratio of 2 + is an element of when the considered submodular function is monotone. To the best of our knowledge, our algorithms achieve the best performance bounds compared to the state-of-the-art approximation algorithms with efficient implementation for the same problem. Finally, we evaluate our algorithms in two concrete submodular data summarization applications for revenue maximization in social networks and image summarization, and the empirical results show that our algorithms outperform the existing ones in terms of both effectiveness and efficiency.

关键词： machine learning data summarization submodular function maximization

来源：评论

学校读者我要写书评

暂无评论

Maximizing h-hop Independently submodular functions Under Connectivity Constraint 41

Maximizing h-hop Independently Submodular Functions Under Co...

引用

41st IEEE Conference on Computer Communications (IEEE INFOCOM)

作者： Xu, Wenzheng Peng, Dezhong Liang, Weifa Jia, Xiaohua Xu, Zichuan Zhou, Pan Wu, Weigang Chen, Xiang Sichuan Univ Coll Comp Sci Chengdu Peoples R China Shenzhen Peng Cheng Lab Shenzhen 518052 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Dalian Univ Technol Sch Software Dalian Peoples R China Huazhong Univ Sci & Technol Sch Cyber Sci & Engn Wuhan Peoples R China Sun Yat Sen Univ Guangzhou 510006 Peoples R China

ISBN: (纸本)9781665458221

This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given K UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem - the h-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with h = 4. We propose a 1 -1/e/2h+3-approximation algorithm for the h-hop independently submodular maximization problem, where e is the base of the natural logarithm. Then, one direct result is a 1-1/e/11 -approximate solution to the MCCP problem with h = 4, which significantly improves its currently best 1-1/e/32-approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.

关键词： UAV communication networks maximum connected coverage problem submodular function maximization approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic Algorithms for submodular maximization Problems 27

Deterministic Algorithms for Submodular Maximization Problem...

引用

27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

ISBN: (纸本)9781510819672

关键词： submodular function maximization derandomization unconstrained submodular maximization

来源：评论

学校读者我要写书评

暂无评论

Complexity Constrained Representation Selection for Dynamic Adaptive Streaming

Complexity Constrained Representation Selection for Dynamic ...

引用

30th IEEE Conference on Visual Communications and Image Processing (VCIP)

作者： Li, Chenglin Toni, Laura Frossard, Pascal Xiong, Hongkai Zou, Junni Ecole Polytech Fed Lausanne EPFL Signal Proc Lab LTS4 Lausanne Switzerland Shanghai Jiao Tong Univ Dept Elect Engn Shanghai Peoples R China Shanghai Univ Sch Commun & Informat Engn Shanghai Peoples R China

ISBN: (纸本)9781509053162

In this paper, we propose a representation selection optimization problem for complexity constrained adaptive video streaming that properly takes into account the different complexity-rate-distortion (C-R-D) characteristics of the videos when implementing rate control for desired representations. Our objective is to maximize the expected video distortion reduction of users, subject not only to encoding rate constraints, but also to complexity constraints. We prove that our optimization problem is a submodular maximization problem with two knapsack constraints. A weighted rate and complexity cost benefit greedy algorithm is then developed to obtain an approximate solution with polynomial time complexity and good approximation performance in simulations.

关键词： Dynamic adaptive video streaming complexity-rate-distortion rate control submodular function maximization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：