Zaloguj się

Gotowe bibliografie tematyczne / Matroid Constraints / Artykuły w czasopismach

Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Matroid Constraints.

Artykuły w czasopismach na temat „Matroid Constraints”

Autor: Grafiati

Data publikacji: 6 września 2023

Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych

Wybierz rodzaj źródła:

Sprawdź 50 najlepszych artykułów w czasopismach naukowych na temat „Matroid Constraints”.

Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.

Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.

Przeglądaj artykuły w czasopismach z różnych dziedzin i twórz odpowiednie bibliografie.

1

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

2

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

3

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

Pełny tekst źródła

Streszczenie:

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].

Style APA, Harvard, Vancouver, ISO itp.

4

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

5

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

6

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

7

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

8

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

9

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

10

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

11

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

12

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

13

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

14

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

15

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

16

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

17

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

18

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

19

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

20

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

21

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

22

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

23

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

24

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

25

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

26

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

27

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

28

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

29

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

30

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

31

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

32

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

33

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

34

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

35

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

36

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

37

Takemura, Kei, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura i 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, nr 11 (18.05.2021): 9791–98. http://dx.doi.org/10.1609/aaai.v35i11.17177.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

38

Reali, Gianluca, i Mauro Femminella. "Two-Layer Network Caching for Different Service Requirements". Future Internet 13, nr 4 (27.03.2021): 85. http://dx.doi.org/10.3390/fi13040085.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

39

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

40

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

Pełny tekst źródła

Style APA, Harvard, Vancouver, ISO itp.

41

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

42

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

43

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

44

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

45

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

46

Chocat, Rudy, Loïc Brevault, Mathieu Balesdent i 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.

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

47

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

48

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

49

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

50

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

Pełny tekst źródła

Streszczenie:

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.

Style APA, Harvard, Vancouver, ISO itp.

Oferujemy zniżki na wszystkie plany premium dla autorów, których prace zostały uwzględnione w tematycznych zestawieniach literatury. Skontaktuj się z nami, aby uzyskać unikalny kod promocyjny!