Discrete Convex Analysis
From MaRDI portal
Publication:4425020
DOI10.1137/1.9780898718508zbMath1029.90055OpenAlexW4206054140MaRDI QIDQ4425020
Publication date: 9 September 2003
Full work available at URL: http://hdl.handle.net/2433/149564
Convex programming (90C25) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items
Influence maximization problem: properties and algorithms, Quadratic M-convex and L-convex functions, Independence systems in gross-substitute valuations, Discrete Fenchel duality for a pair of integrally convex and separable convex functions, Uniqueness of equilibria in atomic splittable polymatroid congestion games, Optimization problems with color-induced budget constraints, Duality for mixed-integer convex minimization, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, The stochastic mitra-wan forestry model: risk neutral and risk averse cases, A cost-scaling algorithm for computing the degree of determinants, Convex analysis and duality over discrete domains, A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds, On the complexity of energy storage problems, Discrete convexity in joint winner property, Resolution of ideals associated to subspace arrangements, Fair integral submodular flows, Cores and Weber sets for fuzzy extensions of cooperative games, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Matching with partially ordered contracts, Matroid rank functions and discrete concavity, Shortest bibranchings and valuated matroid intersection, Algebraic matroids and Frobenius flocks, Gross substitutability: an algorithmic survey, Minimization of an M-convex function, Obstructions to determinantal representability, Identifying combinatorial valuations from aggregate demand, Randomized algorithms for finding the shortest negative cost cycle in networks, An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach, Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees, The quadratic M-convexity testing problem, A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs, Solving discrete systems of nonlinear equations, Ideal multipartite secret sharing schemes, Monotone optimal control for a class of Markov decision processes, A proof of Cunningham's conjecture on restricted subgraphs and jump systems, Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., Topological convexities, selections and fixed points, On \(\omega \)-strongly quasiconvex and \(\omega \)-strongly quasiconcave sequences, Projection and convolution operations for integrally convex functions, Application of M-convex submodular flow problem to mathematical economics, A polynomial-time algorithm for a stable matching problem with linear valuations and bounded side payments, Valuated matroid-based algorithm for submodular welfare problem, A framework of discrete DC programming by discrete convex analysis, Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions, Simpler exchange axioms for M-concave functions on generalized polymatroids, A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions, Core and competitive equilibria: an approach from discrete convex analysis, Envy-free matchings with lower quotas, Largest minimal inversion-complete and pair-complete sets of permutations, Continuous relaxation for discrete DC programming, Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming, Approximating convex functions via non-convex oracles under the relative noise model, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Time bounds for iterative auctions: a unified approach by discrete convex analysis, Buyback problem with discrete concave valuation functions, Inventory rotation of medical supplies for emergency response, Designing matching mechanisms under constraints: an approach from discrete convex analysis, A note on \(M\)-convexity in polyhedral split decomposition of distances, Legendre duality in combinatorial study of matrix pencils, Combinatorial integer labeling theorems on finite sets with applications, Global optimization for first order Markov random fields with submodular priors, Majorization permutahedra and (0,1)-matrices, Conjugacy relationship between M-convex and L-convex functions in continuous variables, \(M\)-convex functions and tree metrics, Walrasian's characterization and a universal ascending auction, On set functions that can be extended to convex functionals, Coordinatewise domain scaling algorithm for M-convex function minimization, Use of primal-dual technique in the network algorithm for two-way contingency tables, A capacity scaling algorithm for M-convex submodular flow, Positively hyperbolic varieties, tropicalization, and positroids, Cone superadditivity of discrete convex functions, Directed discrete midpoint convexity, Relationship of two formulations for shortest bibranchings, Exact bounds for steepest descent algorithms of $L$-convex function minimization, A note on submodular function minimization with covering type linear constraints, Congestion games viewed from M-convexity, Some specially structured assemble-to-order systems, Submodular function minimization, Induction of M-convex functions by linking systems, A Simple Algorithm for Exact Multinomial Tests, Maximizing monotone submodular functions over the integer lattice, The Buneman index via polyhedral split decomposition, Nucleation and growth of lattice crystals, Envy-free matchings with one-sided preferences and matroid constraints, Enumerating Polytropes, Convex and quasiconvex functions in metric graphs, Explicit control of 2D and 3D structural complexity by discrete variable topology optimization method, Traveling salesman games with the Monge property, New algorithms for convex cost tension problem with application to computer vision, A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem, Discrete 2-convex functions, Decreasing minimization on M-convex sets: background and structures, Decreasing minimization on M-convex sets: algorithms and applications, Submodular functions and rooted trees, Adaptive sampling line search for local stochastic optimization with integer variables, Computing valuations of the Dieudonné determinants, Discrete polymatroids, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases, Note on the polyhedral description of the Minkowski sum of two L-convex sets, Staffing decisions for heterogeneous workers with turnover, M♮-Convexity and Its Applications in Operations, Matroids from hypersimplex splits, Algorithmic Aspects of Private Bayesian Persuasion., Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems, Existence of a pure strategy equilibrium in finite symmetric games where payoff functions are integrally concave, Total Variation on a Tree, Power packet transferability via symbol propagation matrix, Submodular Functions: Learnability, Structure, and Optimization, Note on time bounds of two-phase algorithms for \(L\)-convex function minimization, Spatio-Temporal Pricing for Ridesharing Platforms, Logarithmic concavity of Schur and related polynomials, Tropical Gaussians: a brief survey, A Discrete Convex Min-Max Formula for Box-TDI Polyhedra, M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, Logarithmic concavity for morphisms of matroids, Optimal insertion of customers with waiting time targets, Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection., Fundamental polytopes of metric trees via parallel connections of matroids, Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids, Convex analysis in groups and semigroups: a sampler, Scaling, proximity, and optimization of integrally convex functions, Submodular reassignment problem for reallocating agents to tasks with synergy effects, On substitutability and complementarity in discrete choice models, Private Bayesian persuasion, A generalization of the space of complete quadrics, A Note on a Two-Sided Discrete-Concave Market with Possibly Bounded Salaries, A generalized-polymatroid approach to disjoint common independent sets in two matroids, Strategyproof allocation mechanisms with endowments and M-convex distributional constraints, Reconfiguring (non-spanning) arborescences, Uniform semimodular lattices and valuated matroids, Uniform modular lattices and affine buildings, A strongly polynomial algorithm for line search in submodular polyhedra, Unnamed Item, Generalized Permutohedra from Probabilistic Graphical Models, A ranking model for the greedy algorithm and discrete convexity, Convexity result and trees with large Balaban index, Quantitative measure of nonconvexity for black-box continuous functions, Monge properties, discrete convexity and applications, Optimization problems with cone constraints in groups and semigroups: an approach based on image space analysis, A Survey on Covering Supermodular Functions, Theory of Principal Partitions Revisited, Recent Developments in Discrete Convex Analysis, DISCRETE CONCAVITY FOR POTENTIAL GAMES, Lorentzian polynomials, A note on M-convex functions on jump systems, Hybrid Tractable Classes of Constraint Problems, Discrete convexity built on differences, Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States, Consistency of the doctor-optimal equilibrium price vector in job-matching markets, Ideal Secret Sharing Schemes for Useful Multipartite Access Structures, Tropical flag varieties, Compression of \(\mathrm{M}^\natural\)-convex functions -- flag matroids and valuated permutohedra, Optimal Matching Forests and Valuated Delta-Matroids, Submodular Function Minimization under a Submodular Set Covering Constraint, Indivisible commodities and the nonemptiness of the weak core, Local minima, marginal functions, and separating hyperplanes in discrete optimization, Dijkstra's algorithm and L-concave function maximization, Critical duality, A general two-sided matching market with discrete concave utility functions, A note on discrete convexity and local optimality, Competitive equilibria in economies with multiple indivisible and multiple divisible commodities, Agreeable bets with multiple priors, Unnamed Item, Discrete Convex Functions on Graphs and Their Algorithmic Applications, Geometry of gross substitutes valuations, Computing Walrasian equilibria: fast algorithms and structural properties, Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces, The Finite Matroid-Based Valuation Conjecture is False, Fast value iteration: an application of Legendre-Fenchel duality to a class of deterministic dynamic programming problems in discrete time, Even factors, jump systems, and discrete convexity, The discrete separation theorem and price adjustment directions in markets with heterogeneous commodities, Conic relaxation approaches for equal deployment problems, Integrality of subgradients and biconjugates of integrally convex functions, Preservation of Structural Properties in Optimization with Decisions Truncated by Random Variables and Its Applications, Convex Analysis in $\mathbb{Z}^n$ and Applications to Integer Linear Programming, Technical Note—Error Noted in “Order-Based Cost Optimization in Assemble-to-Order Systems” by Lu and Song (2005), CHARACTERIZING DIGITAL STRAIGHTNESS AND DIGITAL CONVEXITY BY MEANS OF DIFFERENCE OPERATORS, A Tractable Class of Binary VCSPs via M-Convex Intersection, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Uniqueness of Equilibria in Atomic Splittable Polymatroid Congestion Games, Optimization Problems with Color-Induced Budget Constraints, Ideal Hierarchical Secret Sharing Schemes, Competitive Equilibrium and Trading Networks: A Network Flow Approach, A note on submodularity preserved involving the rank functions, A survey of fundamental operations on discrete convex functions of various kinds, On basic operations related to network induction of discrete convex functions, Discrete Newton methods for the evacuation problem, Submodular optimization views on the random assignment problem, Discrete convexity, Discrete Concavity and Zeros of Polynomials, Bisubmodular polyhedra, simplicial divisions, and discrete convexity, Market Pricing for Matroid Rank Valuations, Discrete fixed point theorem reconsidered, Substitutes and complements in network flows viewed as discrete convexity, Spaces of Lorentzian and real stable polynomials are Euclidean balls, Minconvex graph factors of prescribed size and a simpler reduction to weighted f-factors, A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications, Coordinating Inventory Control and Pricing Strategies for Perishable Products, On properties of discrete \((r,q)\) and \((s,T)\) inventory systems, Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity, Finding a Stable Allocation in Polymatroid Intersection, Distributionally Robust Linear and Discrete Optimization with Marginals, Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity, Fertilitopes, Dynamic inventory control with payment delay and credit limit, On reachable assignments under dichotomous preferences, The b‐bibranching problem: TDI system, packing, and discrete convexity, Matroids on Eight Elements with the Half-Plane Property and Related Concepts, Recent progress on integrally convex functions, Walrasian equilibria from an optimization perspective: A guide to the literature, Optimal general factor problem and jump system intersection, Subdivisions of generalized permutahedra, Tautological classes of matroids, A common generalization of budget games and congestion games, Product-Mix Auctions and Tropical Geometry, Discrete Midpoint Convexity, The core of a transferable utility game as the solution to a public good market demand problem, Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices, Second‐order necessary optimality conditions for discrete‐time stochastic systems, Tropical medians by transportation, Continuous Relaxation for Discrete DC Programming, Polypositroids, An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint, Equivalence between substitutability and \(\mathrm{M}^\natural\)-concavity for set functions under discrete transfers, Characterization and algorithm for bivariate multi-unit assignment valuations, Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids, Lorentzian polynomials, Segre classes, and adjoint polynomials of convex polyhedral cones, Characterizations of the set of integer points in an integral bisubmodular polyhedron, Combinatorics and Hodge theory, Unnamed Item, A Variant of L♮-Convexity and its Application to Inventory Models with Batch Ordering, Discrete convexity and polynomial solvability in minimum 0-extension problems, When are multidegrees positive?, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, When are multidegrees positive?, Greedy systems of linear inequalities and lexicographically optimal solutions, Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function, Finding Submodularity Hidden in Symmetric Difference, A Characterization of Combinatorial Demand, Multiple Exchange Property for M♮-Concave Functions and Valuated Matroids, Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings, Matroidal Choice Functions, Integral with Respect to a Non Additive Measure: An Overview
