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

A Structure Theory for the Parametric submodular Intersection Problem

MATHEMATICS OF OPERATIONS RESEARCH 2009年第3期34卷 513-521页

作者： Fujishige, Satoru Nagano, Kiyohito Kyoto Univ Math Sci Res Inst Kyoto 6068502 Japan Tokyo Inst Technol Grad Sch Informat Sci & Engn Dept Math & Comp Sci Tokyo 1528552 Japan

A linearly parameterized polymatroid intersection problem appears in the context of principal partitions. We consider a submodular intersection problem on a pair of strong-map sequences of submodular functions, which is an extension of the linearly parameterized polymatroid intersection problem to a nonlinearly parameterized one. We introduce the concept of a basis frame on a finite nonempty set of cardinality n that gives a mapping from the set of all base polyhedra in n-dimensional space into n-dimensional vectors such that each base polyhedron is mapped to one of its bases. We show the existence of a simple universal representation of all optimal solutions of the parameterized submodular intersection problem by means of basis frames.

关键词： submodular functions polymatroid intersection polytopes

来源：评论

学校读者我要写书评

暂无评论

THE submodular SECRETARY PROBLEM GOES LINEAR

引用

SIAM JOURNAL ON COMPUTING 2018年第2期47卷 330-366页

作者： Feldman, Moran Zenklusen, Rico Open Univ Israel Dept Math & Comp Sci Raanana Israel Swiss Fed Inst Technol Dept Math Zurich Switzerland

During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. The interest in MSP is twofold: on the one hand, there are many interesting applications of MSP, and on the other hand, there is strong hope that MSP admits O(1)-competitive algorithms, which is the claim of the well-known matroid secretary conjecture. Partially linked to its numerous applications in online auctions, substantial interest arose also in the study of nonlinear versions of MSP, with a focus on the submodular MSP (SMSP). The fact that submodularity captures the property of diminishing returns, a very natural property for valuation functions, is a key reason for the interest in SMSP. So far, O(1)-competitive algorithms have been obtained for SMSP over some basic matroid classes. This created some hope that, analogously to the matroid secretary conjecture, one may even obtain O(1)-competitive algorithms for SMSP over any matroid. However, up to now, most questions related to SMSP remained open, including whether SMSP may be substantially more difficult than MSP and, more generally, to what extent MSP and, SMSP are related. Our goal is to address these points by presenting general black-box reductions from SMSP to MSP. In particular, we show that any O(1)-competitive algorithm for MSP, even restricted to a particular matroid class, can be transformed in a black-box way to an O(1)-competitive algorithm for SMSP over the same matroid class. This implies that the matroid secretary conjecture is equivalent to the same conjecture for SMSP. Hence, in this sense SMSP is not harder than MSP. Also, to find O(1)-competitive algorithms for SMSP over a particular matroid class, it suffices to consider MSP over the same matroid class. Using our reductions we obtain many first and improved O(1)-competitive algorithms for SMSP over various matroid classes by leveraging known algorithms for MSP. Moreover, our reductions imply an O(log log(rank)

关键词： matroids online algorithms secretary problems submodular functions

来源：评论

学校读者我要写书评

暂无评论

Convex envelopes generated from finitely many compact convex sets

引用

MATHEMATICAL PROGRAMMING 2013年第1-2期137卷 371-408页

作者： Khajavirad, Aida Sahinidis, Nikolaos V. Carnegie Mellon Univ Dept Mech Engn Pittsburgh PA 15213 USA Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA

We consider the problem of constructing the convex envelope of a lower semi-continuous function defined over a compact convex set. We formulate the envelope representation problem as a convex optimization problem for functions whose generating sets consist of finitely many compact convex sets. In particular, we consider nonnegative functions that are products of convex and component-wise concave functions and derive closed-form expressions for the convex envelopes of a wide class of such functions. Several examples demonstrate that these envelopes reduce significantly the relaxation gaps of widely used factorable relaxation techniques.

关键词： Convex envelope Global optimization Factorable relaxations Perspective transformation submodular functions

来源：评论

学校读者我要写书评

暂无评论

submodularity and the traveling salesman problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1999年第3期114卷 489-508页

作者： Herer, YT Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

In this paper we investigate the relationship between traveling salesman tour lengths and submodular functions. This work is motivated by the one warehouse multi-retailer inventory/distribution problem with traveling salesman tour vehicle routing costs. Our goal is to find a submodular function whose values are close to those of optimal tour lengths through a central warehouse and a group of retailers. Our work shows that a submodular approximation to traveling salesman tour lengths whose error is bounded by a constant does not exist. However, we present heuristics that have errors which grow slowly with the number of retailers for the traveling salesman problem in the Euclidean plane. Furthermore, we perform computational tests that show that our submodular approximations of traveling salesman tour lengths have smaller errors than our theoretical worst case analysis would lead us to believe. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： traveling salesman submodular functions

来源：评论

学校读者我要写书评

暂无评论

A refined analysis of submodular Greedy

引用

OPERATIONS RESEARCH LETTERS 2021年第4期49卷 507-514页

作者： Kulik, Ariel Schwartz, Roy Shachnai, Hadas Technion Comp Sci Dept IL-3200003 Haifa Israel

Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on the natural greedy heuristic. We present a novel refined analysis of this greedy heuristic which enables us to: (1) reduce the enumeration in the tight (1 - e(-1))-approximation of [Sviridenko 04] from subsets of size three to two;(2) present an improved upper bound of 0.42945 for the classic algorithm which returns the better between a single element and the output of the greedy heuristic. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： submodular functions Knapsack constraint Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A Test Score-Based Approach to Stochastic submodular Optimization

引用

MANAGEMENT SCIENCE 2021年第2期67卷 1075-1092页

作者： Sekar, Shreyas Vojnovic, Milan Yun, Se-Young Harvard Univ Harvard Business Sch Boston MA 02163 USA London Sch Econ LSE Dept Stat London WC2A 2AE England Korea Adv Inst Sci & Technol KAIST Grad Sch Artificial Intelligence Daejeon 34141 South Korea

We study the canonical problem of maximizing a stochastic submodular function subject to a cardinality constraint, where the goal is to select a subset from a ground set of items with uncertain individual performances to maximize their expected group value. Although near-optimal algorithms have been proposed for this problem, practical concerns regarding scalability, compatibility with distributed implementation, and expensive oracle queries persist in large-scale applications. Motivated by online platforms that rely on individual item scores for content recommendation and team selection, we study a special class of algorithms that select items based solely on individual performance measures known as test scores. The central contribution of this work is a novel and systematic framework for designing test score-based algorithms for a broad class of naturally occurring utility functions. We introduce a new scoring mechanism that we refer to as replication test scores and prove that as long as the objective function satisfies a diminishing-returns condition, one can leverage these scores to compute solutions that are within a constant factor of the optimum. We then extend these scoring mechanisms to the more general stochastic submodular welfare-maximization problem, where the goal is to partition items into groups to maximize the sum of the expected group values. For this more difficult problem, we show that replication test scores can be used to develop an algorithm that approximates the optimal solution up to a logarithmic factor. The techniques presented in this work bridge the gap between the rigorous theoretical work on submodular optimization and simple, scalable heuristics that are useful in certain domains. In particular, our results establish that in many applications involving the selection and assignment of items, one can design algorithms that are intuitive and practically relevant with only a small loss in performance compared with the state-of-the-art ap

关键词： stochastic combinatorial optimization submodular functions welfare maximization test scores

来源：评论

学校读者我要写书评

暂无评论

FINDING submodularITY HIDDEN IN SYMMETRIC DIFFERENCE

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2020年第1期34卷 571-585页

作者： Nakashima, Junpei Yamauchi, Yukiko Kijima, Shuji Yamashita, Masafumi Kyushu Univ Grad Sch Informat Sci & Elect Engn Fukuoka 8190395 Japan

A set function f on a finite set V is submodular if f (X) + (Y) >= f (X boolean OR Y) + f (X boolean AND Y) for any pair X , Y subset of V. The symmetric difference transformation (SD-transformation) of f by a canonical set S subset of V is a set function g given by g(X) = f(X Delta S) for X subset of V, where X Delta S = (X \ S) boolean OR (S \ X) denotes the symmetric difference between X and S. submodularity and SD-transformations are regarded as the counterparts of convexity and affine transformations in a discrete space, respectively. However, submodularity is not preserved under SD-transformations, in contrast to the fact that convexity is invariant under affine transformations. This paper presents a characterization of SD-transformations preserving submodularity. Then, we are concerned with the problem of discovering a canonical set S, given the SD-transformation g of a submodular function f by S, provided that g(X) is given by a function value oracle. A submodular function f on V is said to be strict if f(X) + f(Y) > f(X boolean OR Y) + f(X boolean AND Y) holds whenever both X \ Y and Y \ X are nonempty. We show that the problem is solved by using O(vertical bar V vertical bar) oracle calls when f is strictly submodular, although it requires exponentially many oracle calls in general.

关键词： submodular functions symmetric difference

来源：评论

学校读者我要写书评

暂无评论

Approximate submodularity and its Applications: Subset Selection, Sparse Approximation and Dictionary Selection

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2018年第1期19卷 74-107页

作者： Das, Abhimanyu Kempe, David Google Mountain View CA 94043 USA Univ Southern Calif Dept Comp Sci Los Angeles CA 90089 USA Univ Southern Calif Los Angeles CA 90089 USA

We introduce the submodularity ratio as a measure of how "close" to submodular a set function f is. We show that when f has submodularity ratio gamma, the greedy algorithm for maximizing f provides a (1 - e(-gamma)) approximation. Furthermore, when gamma is bounded away from 0, the greedy algorithm for minimum submodular cover also provides essentially an O(log n) approximation for a universe of n elements. As a main application of this framework, we study the problem of selecting a subset of k random variables from a large set, in order to obtain the best linear prediction of another variable of interest. We analyze the performance of widely used greedy heuristics;in particular, by showing that the submodularity ratio is lower-bounded by the smallest 2 k sparse eigenvalue of the covariance matrix, we obtain the strongest known approximation guarantees for the Forward Regression and Orthogonal Matching Pursuit algorithms. As a second application, we analyze greedy algorithms for the dictionary selection problem, and significantly improve the previously known guarantees. Our theoretical analysis is complemented by experiments on real-world and synthetic data sets;in particular, we focus on an analysis of how tight various spectral parameters and the submodularity ratio are in terms of predicting the performance of the greedy algorithms.

关键词： APPROXIMATION theory GREEDY algorithms submodular functions PROBLEM solving REGRESSION analysis

来源：评论

学校读者我要写书评

暂无评论

On Total Variation Minimization and Surface Evolution Using Parametric Maximum Flows

引用

INTERNATIONAL JOURNAL OF COMPUTER VISION 2009年第3期84卷 288-307页

作者： Chambolle, Antonin Darbon, Jerome Ecole Polytech CNRS CMAP F-91128 Palaiseau France Univ Calif Los Angeles Dept Math Los Angeles CA 90024 USA

In a recent paper Boykov et al. (LNCS, Vol. 3953, pp. 409-422, 2006) propose an approach for computing curve and surface evolution using a variational approach and the geo-cuts method of Boykov and Kolmogorov (International conference on computer vision, pp. 26-33, 2003). We recall in this paper how this is related to well-known approaches for mean curvature motion, introduced by Almgren et al. (SIAM Journal on Control and Optimization 31(2):387-438, 1993) and Luckhaus and Sturzenhecker (Calculus of Variations and Partial Differential Equations 3(2):253-271, 1995), and show how the corresponding problems can be solved with sub-pixel accuracy using Parametric Maximum Flow techniques. This provides interesting algorithms for computing crystalline curvature motion, possibly with a forcing term.

关键词： Crystalline and anisotropic mean curvature flow Variational approaches Total variation submodular functions Max-flow/min-cut Parametric max-flow algorithms

来源：评论

学校读者我要写书评

暂无评论

Semi-streaming algorithms for submodular matroid intersection

引用

MATHEMATICAL PROGRAMMING 2023年第2期197卷 967-990页

作者： Garg, Paritosh Jordan, Linus Svensson, Ola Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland

While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of 2 for the unweighted matching problem, it was only recently that Paz and Schwartzman obtained an analogous result for weighted instances. Their approach is based on the versatile local ratio technique and also applies to generalizations such as weighted hypergraph matchings. However, the framework for the analysis fails for the related problem of weighted matroid intersection and as a result the approximation guarantee for weighted instances did not match the factor 2 achieved by the greedy algorithm for unweighted *** main result closes this gap by developing a semi-streaming algorithm with an approximation guarantee of 2 + epsilon for weighted matroid intersection, improving upon the previous best guarantee of 4 + epsilon. Our techniques also allow us to generalize recent results by Levin and Wajc on submodular maximization subject to matching constraints to that of matroid-intersection constraints. While our algorithm is an adaptation of the local ratio technique used in previous works, the analysis deviates significantly and relies on structural properties of matroid intersection, called kernels. Finally, we also conjecture that our algorithm gives a (k + epsilon) approximation for the intersection of k matroids but prove that new tools are needed in the analysis as the structural properties we use fail for k >= 3.

关键词： Matroid Intersection submodular functions Semi-Streaming Algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：