Log in

Relevant bibliographies by topics / Matroid Constraints / Journal articles

To see the other types of publications on this topic, follow the link: Matroid Constraints.

Journal articles on the topic 'Matroid Constraints'

Author: Grafiati

Published: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Matroid Constraints.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Dror, Amitay, Michal Feldman, and Erel Segal-Halevi. "On Fair Division under Heterogeneous Matroid Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 6 (May 18, 2021): 5312–20. http://dx.doi.org/10.1609/aaai.v35i6.16670.

Full text

Abstract:

We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors, and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints, or allow free disposal of items. An open problem is the existence of EF1 complete allocations among heterogeneous agents, where the heterogeneity is both in the agents' feasibility constraints and in their valuations. In this work, we make progress on this problem by providing positive and negative results for different matroid and valuation types. Among other results, we devise poly-time algorithms for finding EF1 allocations in the following settings: (i) n agents with heterogeneous partition matroids and heterogeneous binary valuations, (ii) 2 agents with heterogeneous partition matroids and heterogeneous valuations, and (iii) at most 3 agents with heterogeneous binary valuations and identical base-orderable matroids.

APA, Harvard, Vancouver, ISO, and other styles

2

Kamiyama, Naoyuki. "MATROID INTERSECTION WITH PRIORITY CONSTRAINTS." Journal of the Operations Research Society of Japan 56, no. 1 (2013): 15–25. http://dx.doi.org/10.15807/jorsj.56.15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Friedrich, Tobias, and Frank Neumann. "Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms." Evolutionary Computation 23, no. 4 (December 2015): 543–58. http://dx.doi.org/10.1162/evco_a_00159.

Full text

Abstract:

Many combinatorial optimization problems have underlying goal functions that are submodular. The classical goal is to find a good solution for a given submodular function f under a given set of constraints. In this paper, we investigate the runtime of a simple single objective evolutionary algorithm called ([Formula: see text]) EA and a multiobjective evolutionary algorithm called GSEMO until they have obtained a good approximation for submodular functions. For the case of monotone submodular functions and uniform cardinality constraints, we show that the GSEMO achieves a [Formula: see text]-approximation in expected polynomial time. For the case of monotone functions where the constraints are given by the intersection of [Formula: see text] matroids, we show that the ([Formula: see text]) EA achieves a ([Formula: see text])-approximation in expected polynomial time for any constant [Formula: see text]. Turning to nonmonotone symmetric submodular functions with [Formula: see text] matroid intersection constraints, we show that the GSEMO achieves a [Formula: see text]-approximation in expected time [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

4

Do, Anh Viet, and Frank Neumann. "Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 14 (May 18, 2021): 12284–92. http://dx.doi.org/10.1609/aaai.v35i14.17458.

Full text

Abstract:

In this study, we consider the subset selection problems with submodular or monotone discrete objective functions under partition matroid constraints where the thresholds are dynamic. We focus on POMC, a simple Pareto optimization approach that has been shown to be effective on such problems. Our analysis departs from singular constraint problems and extends to problems of multiple constraints. We show that previous results of POMC's performance also hold for multiple constraints. Our experimental investigations on random undirected maxcut problems demonstrate POMC's competitiveness against the classical GREEDY algorithm with restart strategy.

APA, Harvard, Vancouver, ISO, and other styles

5

Biswas, Arpita, and Siddharth Barman. "Matroid Constrained Fair Allocation Problem." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 9921–22. http://dx.doi.org/10.1609/aaai.v33i01.33019921.

Full text

Abstract:

We consider the problem of allocating a set of indivisible goods among a group of homogeneous agents under matroid constraints and additive valuations, in a fair manner. We propose a novel algorithm that computes a fair allocation for instances with additive and identical valuations, even under matroid constraints. Our result provides a computational anchor to the existential result of the fairness notion, called EF1 (envy-free up to one good) by Biswas and Barman in this setting. We further provide examples to show that the fairness notions stronger than EF1 does not always exist in this setting.

APA, Harvard, Vancouver, ISO, and other styles

6

Gu, Yu-Ran, Chao Bian, and Chao Qian. "Submodular Maximization under the Intersection of Matroid and Knapsack Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 3959–67. http://dx.doi.org/10.1609/aaai.v37i4.25510.

Full text

Abstract:

Submodular maximization arises in many applications, and has attracted a lot of research attentions from various areas such as artificial intelligence, finance and operations research. Previous studies mainly consider only one kind of constraint, while many real-world problems often involve several constraints. In this paper, we consider the problem of submodular maximization under the intersection of two commonly used constraints, i.e., k-matroid constraint and m-knapsack constraint, and propose a new algorithm SPROUT by incorporating partial enumeration into the simultaneous greedy framework. We prove that SPROUT can achieve a polynomial-time approximation guarantee better than the state-of-the-art algorithms. Then, we introduce the random enumeration and smooth techniques into SPROUT to improve its efficiency, resulting in the SPROUT++ algorithm, which can keep a similar approximation guarantee. Experiments on the applications of movie recommendation and weighted max-cut demonstrate the superiority of SPROUT++ in practice.

APA, Harvard, Vancouver, ISO, and other styles

7

Suksompong, Warut. "Constraints in fair division." ACM SIGecom Exchanges 19, no. 2 (November 2021): 46–61. http://dx.doi.org/10.1145/3505156.3505162.

Full text

Abstract:

The fair allocation of resources to interested agents is a fundamental problem in society. While the majority of the fair division literature assumes that all allocations are feasible, in practice there are often constraints on the allocation that can be chosen. In this survey, we discuss fairness guarantees for both divisible (cake cutting) and indivisible resources under several common types of constraints, including connectivity, cardinality, matroid, geometric, separation, budget, and conflict constraints. We also outline a number of open questions and directions.

APA, Harvard, Vancouver, ISO, and other styles

8

Király, Csaba, Zoltán Szigeti, and Shin-ichi Tanigawa. "Packing of arborescences with matroid constraints via matroid intersection." Mathematical Programming 181, no. 1 (April 2, 2019): 85–117. http://dx.doi.org/10.1007/s10107-019-01377-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Srinivas, Mandayam A. "Matroid optimization with generalized constraints." Discrete Applied Mathematics 63, no. 2 (November 1995): 161–74. http://dx.doi.org/10.1016/0166-218x(94)00031-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Ramalingam, Srikumar, Arvind Raghunathan, and Daniel Nikovski. "Submodular Function Maximization for Group Elevator Scheduling." Proceedings of the International Conference on Automated Planning and Scheduling 27 (June 5, 2017): 233–41. http://dx.doi.org/10.1609/icaps.v27i1.13799.

Full text

Abstract:

We propose a novel approach for group elevator scheduling by formulating it as the maximization of submodular function under a matroid constraint. In particular, we propose to model the total waiting time of passengers using a quadratic Boolean function. The unary and pairwise terms in the function denote the waiting time for single and pairwise allocation of passengers to elevators, respectively. We show that this objective function is submodular. The matroid constraints ensure that every passenger is allocated to exactly one elevator. We use a greedy algorithm to maximize the submodular objective function, and derive provable guarantees on the optimality of the solution. We tested our algorithm using Elevate 8, a commercial-grade elevator simulator that allows simulation with a wide range of elevator settings. We achieve significant improvement over the existing algorithms.

APA, Harvard, Vancouver, ISO, and other styles

11

Chaturvedi, Anamay, Huy Lê Nguyễn, and Lydia Zakynthinou. "Differentially Private Decomposable Submodular Maximization." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 8 (May 18, 2021): 6984–92. http://dx.doi.org/10.1609/aaai.v35i8.16860.

Full text

Abstract:

We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem (Papadimitriou, Schapira, and Singer 2008). Previous work by Gupta et al. (2010) gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating improved empirical performance.

APA, Harvard, Vancouver, ISO, and other styles

12

Bengs, Daniel, and Ulf Kröhne. "Adaptive Item Selection Under Matroid Constraints." Journal of Computerized Adaptive Testing 6, no. 2 (August 7, 2018): 15–36. http://dx.doi.org/10.7333/1808-0602015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Kakimura, Naonori, and Mizuyo Takamatsu. "Matching Problems with Delta-Matroid Constraints." SIAM Journal on Discrete Mathematics 28, no. 2 (January 2014): 942–61. http://dx.doi.org/10.1137/110860070.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Liu, Qian, Kemin Yu, Min Li, and Yang Zhou. "$k$-Submodular Maximization with a Knapsack Constraint and $p$ Matroid Constraints." Tsinghua Science and Technology 28, no. 5 (October 2023): 896–905. http://dx.doi.org/10.26599/tst.2022.9010039.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Friedrich, Tobias, Andreas Göbel, Frank Neumann, Francesco Quinzan, and Ralf Rothenberger. "Greedy Maximization of Functions with Bounded Curvature under Partition Matroid Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2272–79. http://dx.doi.org/10.1609/aaai.v33i01.33012272.

Full text

Abstract:

We investigate the performance of a deterministic GREEDY algorithm for the problem of maximizing functions under a partition matroid constraint. We consider non-monotone submodular functions and monotone subadditive functions. Even though constrained maximization problems of monotone submodular functions have been extensively studied, little is known about greedy maximization of non-monotone submodular functions or monotone subadditive functions. We give approximation guarantees for GREEDY on these problems, in terms of the curvature. We find that this simple heuristic yields a strong approximation guarantee on a broad class of functions. We discuss the applicability of our results to three real-world problems: Maximizing the determinant function of a positive semidefinite matrix, and related problems such as the maximum entropy sampling problem, the constrained maximum cut problem on directed graphs, and combinatorial auction games. We conclude that GREEDY is well-suited to approach these problems. Overall, we present evidence to support the idea that, when dealing with constrained maximization problems with bounded curvature, one needs not search for (approximate) monotonicity to get good approximate solutions.

APA, Harvard, Vancouver, ISO, and other styles

16

Kamiyama, Naoyuki. "Popular Matchings with Ties and Matroid Constraints." SIAM Journal on Discrete Mathematics 31, no. 3 (January 2017): 1801–19. http://dx.doi.org/10.1137/15m104918x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Krishnaswamy, Ravishankar, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna Saha. "Facility Location with Matroid or Knapsack Constraints." Mathematics of Operations Research 40, no. 2 (May 2015): 446–59. http://dx.doi.org/10.1287/moor.2014.0678.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Gong, Suning, Qingqin Nong, Wenjing Liu, and Qizhi Fang. "Parametric monotone function maximization with matroid constraints." Journal of Global Optimization 75, no. 3 (July 3, 2019): 833–49. http://dx.doi.org/10.1007/s10898-019-00800-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Bérczi, Kristóf, Tamás Király, and Yusuke Kobayashi. "Covering Intersecting Bi-set Families under Matroid Constraints." SIAM Journal on Discrete Mathematics 30, no. 3 (January 2016): 1758–74. http://dx.doi.org/10.1137/15m1049099.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Zhang, Zhenliang, Yuan Wang, Edwin K. P. Chong, and Ali Pezeshki. "Subspace Selection for Projection Maximization With Matroid Constraints." IEEE Transactions on Signal Processing 65, no. 5 (March 1, 2017): 1339–51. http://dx.doi.org/10.1109/tsp.2016.2634544.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Kamiyama, Naoyuki. "Pareto Stable Matchings under One-Sided Matroid Constraints." SIAM Journal on Discrete Mathematics 33, no. 3 (January 2019): 1431–51. http://dx.doi.org/10.1137/17m1149717.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Kamiyama, Naoyuki. "A CHARACTERIZATION OF WEIGHTED POPULAR MATCHINGS UNDER MATROID CONSTRAINTS." Journal of the Operations Research Society of Japan 61, no. 1 (2018): 2–17. http://dx.doi.org/10.15807/jorsj.61.2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Lee, Jon, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. "Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints." SIAM Journal on Discrete Mathematics 23, no. 4 (January 2010): 2053–78. http://dx.doi.org/10.1137/090750020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Kamiyama, Naoyuki. "The popular matching and condensation problems under matroid constraints." Journal of Combinatorial Optimization 32, no. 4 (October 19, 2015): 1305–26. http://dx.doi.org/10.1007/s10878-015-9965-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Han, Kai, Yuntian He, Alex X. Liu, Shaojie Tang, and He Huang. "Differentially Private and Budget-Limited Bandit Learning over Matroids." INFORMS Journal on Computing 32, no. 3 (July 2020): 790–804. http://dx.doi.org/10.1287/ijoc.2019.0903.

Full text

Abstract:

We propose the first budget-limited multi-armed bandit (BMAB) algorithm subject to a union of matroid constraints in arm pulling, while at the same time achieving differential privacy. Our model generalizes the arm-pulling models studied in prior BMAB schemes, and it can be used to address many practical problems such as network backbone construction and dynamic pricing in crowdsourcing. We handle the exploitation versus exploration tradeoff in our BMAB problem by exploiting the combinatorial structures of matroids, and reduce the searching complexity of arm selection based on a divide-and-conquer approach. Our algorithm achieves a uniform logarithmic regret bound with respect to B and ɛ-differential privacy, where B is the budget for pulling the arms with random costs. Without differential privacy, our algorithm achieves a uniform logarithmic regret bound with respect to B, which advances the asymptotic regret bounds achieved by prior BMAB algorithms. We performed side-by-side comparisons with prior schemes in our experiments. Experimental results show that our purely-combinatorial algorithm not only achieves significantly better regret performance, but also is more than 20 times faster than prior BMAB schemes, which use time-consuming LP-solving techniques.

APA, Harvard, Vancouver, ISO, and other styles

26

Kamiyama, Naoyuki. "Envy-free matchings with one-sided preferences and matroid constraints." Operations Research Letters 49, no. 5 (September 2021): 790–94. http://dx.doi.org/10.1016/j.orl.2021.08.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Kamiyama, Naoyuki. "Popular matchings with two-sided preference lists and matroid constraints." Theoretical Computer Science 809 (February 2020): 265–76. http://dx.doi.org/10.1016/j.tcs.2019.12.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Xue, Jue. "The optimal base of a matroid/with tree-type constraints." Acta Mathematicae Applicatae Sinica 4, no. 2 (May 1988): 97–108. http://dx.doi.org/10.1007/bf02006057.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Wu, Lin, Yang Wang, John Shepherd, and Xiang Zhao. "Max-sum diversification on image ranking with non-uniform matroid constraints." Neurocomputing 118 (October 2013): 10–20. http://dx.doi.org/10.1016/j.neucom.2013.02.008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Ceccarello, Matteo, Andrea Pietracaprina, and Geppino Pucci. "A General Coreset-Based Approach to Diversity Maximization under Matroid Constraints." ACM Transactions on Knowledge Discovery from Data 14, no. 5 (August 21, 2020): 1–27. http://dx.doi.org/10.1145/3402448.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Zheng, Jiping, Yuan Ma, Wei Ma, Yanhao Wang, and Xiaoyang Wang. "Happiness maximizing sets under group fairness constraints." Proceedings of the VLDB Endowment 16, no. 2 (October 2022): 291–303. http://dx.doi.org/10.14778/3565816.3565830.

Full text

Abstract:

Finding a happiness maximizing set (HMS) from a database, i.e., selecting a small subset of tuples that preserves the best score with respect to any nonnegative linear utility function, is an important problem in multi-criteria decision-making. When an HMS is extracted from a set of individuals to assist data-driven algorithmic decisions such as hiring and admission, it is crucial to ensure that the HMS can fairly represent different groups of candidates without bias and discrimination. However, although the HMS problem was extensively studied in the database community, existing algorithms do not take group fairness into account and may provide solutions that under-represent some groups. In this paper, we propose and investigate a fair variant of HMS (FairHMS) that not only maximizes the minimum happiness ratio but also guarantees that the number of tuples chosen from each group falls within predefined lower and upper bounds. Similar to the vanilla HMS problem, we show that FairHMS is NP-hard in three and higher dimensions. Therefore, we first propose an exact interval cover-based algorithm called IntCov for FairHMS on two-dimensional databases. Then, we propose a bicriteria approximation algorithm called BiGreedy for FairHMS on multi-dimensional databases by transforming it into a submodular maximization problem under a matroid constraint. We also design an adaptive sampling strategy to improve the practical efficiency of BiGreedy. Extensive experiments on real-world and synthetic datasets confirm the efficacy and efficiency of our proposal.

APA, Harvard, Vancouver, ISO, and other styles

32

Agrawal, Akanksha, Tanmay Inamdar, Saket Saurabh, and Jie Xue. "Clustering What Matters: Optimal Approximation for Clustering with Outliers." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 6 (June 26, 2023): 6666–74. http://dx.doi.org/10.1609/aaai.v37i6.25818.

Full text

Abstract:

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k and m, the clustering with outliers aims to exclude m points from X, and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m (i.e., an algorithm with running time of the form f(k, m) * poly(n) for some function f), that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.

APA, Harvard, Vancouver, ISO, and other styles

33

Rafiey, Akbar, and Yuichi Yoshida. "Sparsification of Decomposable Submodular Functions." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (June 28, 2022): 10336–44. http://dx.doi.org/10.1609/aaai.v36i9.21275.

Full text

Abstract:

Submodular functions are at the core of many machine learning and data mining tasks. The underlying submodular functions for many of these tasks are decomposable, i.e., they are sum of several simple submodular functions. In many data intensive applications, however, the number of underlying submodular functions in the original function is so large that we need prohibitively large amount of time to process it and/or it does not even fit in the main memory. To overcome this issue, we introduce the notion of sparsification for decomposable submodular functions whose objective is to obtain an accurate approximation of the original function that is a (weighted) sum of only a few submodular functions. Our main result is a polynomial-time randomized sparsification algorithm such that the expected number of functions used in the output is independent of the number of underlying submodular functions in the original function. We also study the effectiveness of our algorithm under various constraints such as matroid and cardinality constraints. We complement our theoretical analysis with an empirical study of the performance of our algorithm.

APA, Harvard, Vancouver, ISO, and other styles

34

Esfandiari, Hossein, MohammadTaghi HajiAghayi, Brendan Lucier, and Michael Mitzenmacher. "Online Pandora’s Boxes and Bandits." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 1885–92. http://dx.doi.org/10.1609/aaai.v33i01.33011885.

Full text

Abstract:

We consider online variations of the Pandora’s box problem (Weitzman 1979), a standard model for understanding issues related to the cost of acquiring information for decision-making. Our problem generalizes both the classic Pandora’s box problem and the prophet inequality framework. Boxes are presented online, each with a random value and cost drawn jointly from some known distribution. Pandora chooses online whether to open each box given its cost, and then chooses irrevocably whether to keep the revealed prize or pass on it. We aim for approximation algorithms against adversaries that can choose the largest prize over any opened box, and use optimal offline policies to decide which boxes to open (without knowledge of the value inside)1. We consider variations where Pandora can collect multiple prizes subject to feasibility constraints, such as cardinality, matroid, or knapsack constraints. We also consider variations related to classic multi-armed bandit problems from reinforcement learning. Our results use a reduction-based framework where we separate the issues of the cost of acquiring information from the online decision process of which prizes to keep. Our work shows that in many scenarios, Pandora can achieve a good approximation to the best possible performance.

APA, Harvard, Vancouver, ISO, and other styles

35

Li, Bo, Xiaowei Wu, Chenyang Xu, and Ruilong Zhang. "Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 5 (June 26, 2023): 5730–38. http://dx.doi.org/10.1609/aaai.v37i5.25711.

Full text

Abstract:

Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1-o(1)) ln k)-approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our problem to submodular objective functions and Matroid rank constraints.

APA, Harvard, Vancouver, ISO, and other styles

36

Katoh, Naoki, and Shin-ichi Tanigawa. "Rooted-Tree Decompositions with Matroid Constraints and the Infinitesimal Rigidity of Frameworks with Boundaries." SIAM Journal on Discrete Mathematics 27, no. 1 (January 2013): 155–85. http://dx.doi.org/10.1137/110846944.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Takemura, Kei, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, and Ken-ichi Kawarabayashi. "Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 11 (May 18, 2021): 9791–98. http://dx.doi.org/10.1609/aaai.v35i11.17177.

Full text

Abstract:

The contextual combinatorial semi-bandit problem with linear payoff functions is a decision-making problem in which a learner chooses a set of arms with the feature vectors in each round under given constraints so as to maximize the sum of rewards of arms. Several existing algorithms have regret bounds that are optimal with respect to the number of rounds T. However, there is a gap of Õ(max(√d, √k)) between the current best upper and lower bounds, where d is the dimension of the feature vectors, k is the number of the chosen arms in a round, and Õ(·) ignores the logarithmic factors. The dependence of k and d is of practical importance because k may be larger than T in real-world applications such as recommender systems. In this paper, we fill the gap by improving the upper and lower bounds. More precisely, we show that the C2UCB algorithm proposed by Qin, Chen, and Zhu (2014) has the optimal regret bound Õ(d√kT + dk) for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C2UCB algorithm and demonstrate that it enjoys the optimal regret bound for a more general problem that can take into account other objectives simultaneously. We also show that our technique would be applicable to related problems. Numerical experiments support our theoretical results and considerations.

APA, Harvard, Vancouver, ISO, and other styles

38

Reali, Gianluca, and Mauro Femminella. "Two-Layer Network Caching for Different Service Requirements." Future Internet 13, no. 4 (March 27, 2021): 85. http://dx.doi.org/10.3390/fi13040085.

Full text

Abstract:

Network caching is a technique used to speed-up user access to frequently requested contents in complex data networks. This paper presents a two-layer overlay network caching system for content distribution. It is used to define some caching scenarios with increasing complexity, which refers to real situations, including mobile 5G connectivity. For each scenario our aim is to maximize the hit ratio, which leads to the formulation of NP-complete optimization problems. The heuristic solutions proposed are based on the theory of the maximization of monotone submodular functions under matroid constraints. After the determination of the approximation ratio of the greedy heuristic algorithms proposed, a numerical performance analysis is shown. This analysis includes a comparison with the Least-Frequently Used (LFU) eviction strategy adapted to the analyzed systems. Results show very good performance, under the hypotheses of either known or unknown popularity of contents.

APA, Harvard, Vancouver, ISO, and other styles

39

Gölz, Paul, and Ariel D. Procaccia. "Migration as Submodular Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 549–56. http://dx.doi.org/10.1609/aaai.v33i01.3301549.

Full text

Abstract:

Migration presents sweeping societal challenges that have recently attracted significant attention from the scientific community. One of the prominent approaches that have been suggested employs optimization and machine learning to match migrants to localities in a way that maximizes the expected number of migrants who find employment. However, it relies on a strong additivity assumption that, we argue, does not hold in practice, due to competition effects; we propose to enhance the data-driven approach by explicitly optimizing for these effects. Specifically, we cast our problem as the maximization of an approximately submodular function subject to matroid constraints, and prove that the worst-case guarantees given by the classic greedy algorithm extend to this setting. We then present three different models for competition effects, and show that they all give rise to submodular objectives. Finally, we demonstrate via simulations that our approach leads to significant gains across the board.

APA, Harvard, Vancouver, ISO, and other styles

40

Huang, Chien-Chung, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida. "Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model." SIAM Journal on Discrete Mathematics 36, no. 1 (February 8, 2022): 355–82. http://dx.doi.org/10.1137/20m1357317.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Siddiqui, Zaheer A., Rati Shukla, Amrita Jyoti, Ayushi Prakash, and Mayur Rahul. "On the Connection of Matroids and Greedy Algorithms." International Journal of Electrical and Electronics Research 10, no. 2 (June 30, 2022): 126–30. http://dx.doi.org/10.37391/ijeer.100213.

Full text

Abstract:

Matroids are the combinatorial structure and Greedy algorithmic methods always produces optimal solutions for these mathematical models. A greedy method always selects the option that looks best at each step of process of finding optimal solution. In other words, it selects a choice which is optimal choice locally in such a strategy that this locally chosen option may direct to a solution that will be globally optimal. It is true that while selecting locally optimal solution at each stage, Greedy algorithms may not always yield optimal solutions [1-2], but if we can transform an unknown problem into matroid structure, then there must be a greedy algorithm that will always lead optimal solution for that unknown problem. The range of solutions provided by Greedy is large as compared to the applicability of the Matroid structure. In other words the problems that can be translated into Matroid structure is proper subset of set of all problems whether Greedy algorithm produces optimal solution. Matroid structure thus ensures the global optimal solution one can obtain with help of Greedy approach. We study various logarithmic and linear hierarchical based mathematical models from divergence sources to maximize our information for research purposes. We analyze the time complexity and provide constrains over the upper/lower bounds in correspondence with the optimal (maximum/minimum) solution. We try to establish the relationship between the maximization of information divergences, the optimal-likelihood theory, and classified sharing is instituted. We propose integration of unknown rough sets to matroids in this paper. Particularly, we devise methodically the upper and lower tightening bounds on rough matroids which may expand up to the generic combinatorial matroid structure. The relationships are established by the upper and lower tightening bounds approximations of generalized combinatorial rough sets based on different interdependent relation sets, respectively [4]. As we define the generalized lower/upper bounds for rough matroid, we define a new structure for lower/upper greedoid leading to generalization of the greedoid [5]. Additionally, based on the new established relation, the generalized rough set also provides a theory of poset matroid.

APA, Harvard, Vancouver, ISO, and other styles

42

Gatmiry, Khashayar, and Manuel Gomez-Rodriguez. "The Network Visibility Problem." ACM Transactions on Information Systems 40, no. 2 (April 30, 2022): 1–42. http://dx.doi.org/10.1145/3460475.

Full text

Abstract:

Social media is an attention economy where broadcasters are constantly competing for attention in their followers’ feeds. Broadcasters are likely to elicit greater attention from their followers if their posts remain visible at the top of their followers’ feeds for a longer period of time. However, this depends on the rate at which their followers receive information in their feeds, which in turn depends on the broadcasters they follow. Motivated by this observation and recent calls for fairness of exposure in social networks, in this article, we look at the task of recommending links from the perspective of visibility optimization. Given a set of candidate links provided by a link recommendation algorithm, our goal is to find a subset of those links that would provide the highest visibility to a set of broadcasters. To this end, we first show that this problem reduces to maximizing a nonsubmodular nondecreasing set function under matroid constraints. Then, we show that the set function satisfies a notion of approximate submodularity that allows the standard greedy algorithm to enjoy theoretical guarantees. Experiments on both synthetic and real data gathered from Twitter show that the greedy algorithm is able to consistently outperform several competitive baselines.

APA, Harvard, Vancouver, ISO, and other styles

43

Wu, Jingyan, Jiawei Zhang, and Yuefeng Ji. "DCEC: D2D-Enabled Cost-Aware Cooperative Caching in MEC Networks." Electronics 12, no. 9 (April 24, 2023): 1974. http://dx.doi.org/10.3390/electronics12091974.

Full text

Abstract:

Various kinds of powerful intelligent mobile devices (MDs) need to access multimedia content anytime and anywhere, which places enormous pressure on mobile wireless networks. Fetching content from remote sources may introduce overly long accessing delays, which will result in a poor quality of experience (QoE). In this article, we considered the advantages of combining mobile/multi-access edge computing (MEC) with device-to-device (D2D) technologies. We propose a D2D-enabled cooperative edge caching (DCEC) architecture to reduce the delay of accessing content. We designed the DCEC caching management scheme through the maximization of a monotone submodular function under matroid constraints. The DCEC scheme includes a proactive cache placement algorithm and a reactive cache replacement algorithm. Thus, we obtained an optimal content caching and content update, which minimized the average delay cost of fetching content files. Finally, simulations compared the DCEC network architecture with the MEC and D2D networks and the DCEC caching management scheme with the least-frequently used and least-recently used scheme. The numerical results verified that the proposed DCEC scheme was effective at improving the cache hit ratio and the average delay cost. Therefore, the users’ QoE was improved.

APA, Harvard, Vancouver, ISO, and other styles

44

Blajer, W., D. Bestle, and W. Schiehlen. "An Orthogonal Complement Matrix Formulation for Constrained Multibody Systems." Journal of Mechanical Design 116, no. 2 (June 1, 1994): 423–28. http://dx.doi.org/10.1115/1.2919396.

Full text

Abstract:

A method is proposed for the automatic generation of an orthogonal complement matrix to the constraint matrix for the dynamic analysis of constrained multibody systems. The clue for this method lies in the determination of local constraint matrices and their orthogonal complements relative to the local reference frames of particular constrained points. These matrices are then transformed into the system’s configuration space in order to form the final constraint matrix and its orthogonal complement. The avoidance of singularities in the formulation is discussed. The method is especially suited for the dynamic analysis of multibody systems with many constraints and/or closed-loops.

APA, Harvard, Vancouver, ISO, and other styles

45

Agrawal, R., G. L. Kinzel, R. Srinivasan, and K. Ishii. "Engineering Constraint Management Based on an Occurrence Matrix Approach." Journal of Mechanical Design 115, no. 1 (March 1, 1993): 103–9. http://dx.doi.org/10.1115/1.2919305.

Full text

Abstract:

In many mechanical systems, the mathematical model can be characterized by m nonlinear equations in n unknowns. The m equations could be either equality constraints or active inequality constraints in a constrained optimization framework. In either case, the mathematical model consists of (n-m) degrees of freedom, and (n-m) unknowns must be specified before the system can be analyzed. In the past, designers have often fixed the set of (n-m) specification variables and computed the remaining n variables using the n equations. This paper presents constraint management algorithms that give the designer complete freedom in the choice of design specifications. An occurrence matrix is used to store relationships among design parameters and constraints, to identify dependencies among the variables, and to help prevent redundant specification. The interactive design of a torsion bar spring is used to illustrate constraint management concepts.

APA, Harvard, Vancouver, ISO, and other styles

46

Chocat, Rudy, Loïc Brevault, Mathieu Balesdent, and Sébastien Defoort. "Modified Covariance Matrix Adaptation – Evolution Strategy algorithm for constrained optimization under uncertainty, application to rocket design." International Journal for Simulation and Multidisciplinary Design Optimization 6 (2015): A1. http://dx.doi.org/10.1051/smdo/2015001.

Full text

Abstract:

The design of complex systems often induces a constrained optimization problem under uncertainty. An adaptation of CMA-ES(λ, μ) optimization algorithm is proposed in order to efficiently handle the constraints in the presence of noise. The update mechanisms of the parametrized distribution used to generate the candidate solutions are modified. The constraint handling method allows to reduce the semi-principal axes of the probable research ellipsoid in the directions violating the constraints. The proposed approach is compared to existing approaches on three analytic optimization problems to highlight the efficiency and the robustness of the algorithm. The proposed method is used to design a two stage solid propulsion launch vehicle.

APA, Harvard, Vancouver, ISO, and other styles

47

SHIOURA, AKIYOSHI. "ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS." Discrete Mathematics, Algorithms and Applications 01, no. 01 (March 2009): 1–23. http://dx.doi.org/10.1142/s1793830909000063.

Full text

Abstract:

We consider the problem of maximizing a nondecreasing submodular set function under a matroid constraint. Recently, Calinescu et al. (2007) proposed an elegant framework for the approximation of this problem, which is based on the pipage rounding technique by Ageev and Sviridenko (2004), and showed that this framework indeed yields a (1 - 1/e)-approximation algorithm for the class of submodular functions which are represented as the sum of weighted rank functions of matroids. This paper sheds a new light on this result from the viewpoint of discrete convex analysis by extending it to the class of submodular functions which are the sum of M ♮-concave functions. M ♮-concave functions are a class of discrete concave functions introduced by Murota and Shioura (1999), and contain the class of the sum of weighted rank functions as a proper subclass. Our result provides a better understanding for why the pipage rounding algorithm works for the sum of weighted rank functions. Based on the new observation, we further extend the approximation algorithm to the maximization of a nondecreasing submodular function over an integral polymatroid. This extension has an application in multi-unit combinatorial auctions.

APA, Harvard, Vancouver, ISO, and other styles

48

SITHARAM, MEERA, YONG ZHOU, and JÖRG PETERS. "RECONCILING CONFLICTING COMBINATORIAL PREPROCESSORS FOR GEOMETRIC CONSTRAINT SYSTEMS." International Journal of Computational Geometry & Applications 20, no. 06 (December 2010): 631–51. http://dx.doi.org/10.1142/s0218195910003463.

Full text

Abstract:

Polynomial equation systems arising from real applications often have associated combinatorial information, expressible as graphs and underlying matroids. To simplify the system and improve its numerical robustness before attempting to solve it with numeric-algebraic techniques, solvers can employ graph algorithms to extract substructures satisfying or optimizing various combinatorial properties. When there are underlying matroids, these algorithms can be greedy and efficient. In practice, correct and effective merging of the outputs of different graph algorithms to simultaneously satisfy their goals is a key challenge. This paper merges and improves two highly effective but separate graph-based algorithms that preprocess systems for resolving the relative position and orientation of a collection of incident rigid bodies. Such collections naturally arise in many situations, for example in the recombination of decomposed large geometric constraint systems. Each algorithm selects a subset of incidences, one to optimize algebraic complexity of a parametrized system, the other to obtain a well-formed system that is robust against numerical errors. Both algorithms are greedy and can be proven correct by revealing underlying matroids. The challenge is that the output of the first algorithm is not guaranteed to be extensible to a well-formed system, while the output of the second may not have optimal algebraic complexity. Here we show how to reconcile the two algorithms by revealing well-behaved maps between the associated matroids.

APA, Harvard, Vancouver, ISO, and other styles

49

Chen, Ying, Bei Kang, Min-Li Li, Li-Fang Wang, and Chun-Hong Zhang. "Correlators in the β-deformed Gaussian Hermitian and complex matrix models." International Journal of Modern Physics A 34, no. 33 (November 30, 2019): 1950221. http://dx.doi.org/10.1142/s0217751x1950221x.

Full text

Abstract:

We investigate the [Formula: see text]-deformed Gaussian Hermitian and [Formula: see text] complex matrix models which are defined as the eigenvalue integral representations. Their [Formula: see text] constraints are constructed such that the constraint operators yield the same [Formula: see text][Formula: see text]-algebra. When particularized to the Virasoro constraints in the [Formula: see text] constraints, the corresponding constraint operators yield the Witt algebra and null 3-algebra. By solving our Virasoro constraints, we derive the formulas for correlators in these two [Formula: see text]-deformed matrix models, respectively.

APA, Harvard, Vancouver, ISO, and other styles

50

Aziz, Haris, Péter Biró, and Makoto Yokoo. "Matching Market Design with Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 11 (June 28, 2022): 12308–16. http://dx.doi.org/10.1609/aaai.v36i11.21495.

Full text

Abstract:

Two-sided matching is an important research area that has had a major impact on the design of real-world matching markets. One consistent feature in many of the real-world applications is that they impose new feasibility constraints that lead to research challenges. We survey developments in the field of two-sided matching with various constraints, including those based on regions, diversity, multi-dimensional capacities, and matroids.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!